Traverse a binary tree from bottom up with leaf nodes regarded at the same level
[Update] Nov 4, 2023: At the time I was writting this post, I wasn't aware that this traversing method is actually called Post-order Depth First Traversals. You can learn more from here.
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 a match chart or tournament schedule. Where we can regard all the players as the leaves of the tree.
Now, let's 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. We can observe that some paths from the root to the leaf have less level than others (e.g. 0-2 vs. 0-1-3).
So the first step is to define a function to get its max depth 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 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 to this. Please let me know if you have seen something like this before so I can know the exact name of this traversal method.
