Traverse a binary tree from bottom up with leaf nodes regarded at the same level

Frontend Jan 11, 2022

We have many ways of traversing a binary tree. Like in-order traversal, pre-order traversal, post-order traversal, level order traversal and so on.

It is not difficult to implement a reverse level order traversal method. However, considering the following scenario: What if we want to label all the nodes from bottom to up in sequence, where we regard all the leaf nodes are at the same level?

To better illustrate the problem, we take the example of match chart, or tournament schedule. Where we can regard all the players as the leaves of the tree.

By Michael Buchino, from https://blog.buchino.net/post/45641231359/futura-bracket, attributed by CC BY-NC-SA 3.0

Now, lets abstract the problem by using some examples:

Input:

     0
   /   \
  1     2
 / \ 
3   4

Output: [3, 4, 2, 1, 0]


Input: 

     0
   /   \
  1     2
 / \   / \
3   4 5   6

Output: [3, 4, 5, 6, 1, 2, 0]

It is clear that we should traverse the nodes from bottom to up, thus from leaf to root. Where we can observed that the leaf has no children, thus has the minimum levels of children, to the root that has most level of children. So the first step is to define a function to get its levels of children (the method below should actually be renamed):

    function getDepth(node) {
      if (node == null) return 0;
      else {
        /* compute the depth of each subtree */
        let lDepth = this.maxDepth(node.left);
        let rDepth = this.maxDepth(node.right);

        /* use the larger one */
        if (lDepth > rDepth) return lDepth + 1;
        else return rDepth + 1;
      }
    },

Also we can write the main function:

    function leafNodeFirstLevelTraversal(node) {
        let maxDepth = this.getDepth(node)

        for (let i = 0; i <= maxDepth; i++) {
            this.leafNodeFirstLevelTraversalSub(node, i)
        }
    },

We will use a recursion to handle the real work:

    function leafNodeFirstLevelTraversalSub(node, level) {
        if (node == null) return;

        const childrenDepth = this.getDepth(node) - 1

        if (childrenDepth == level) {
            console.log(node.data)
        }

        else {
            this.leafNodeFirstLevelTraversalSub(node.left, level);
            this.leafNodeFirstLevelTraversalSub(node.right, level);
        }
    },

p.s. I searched all over the internet but find nothing related on this. Please let me know if you have seen something like this before so I can know the exact name of this traversal method.

Tags

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.