How is Recursion Populating SubTree Values in Binary Tree?

Question

I'm working on the Leetcode problem 110. Balanced Binary Tree and I'm confused on how the subtree values are getting populated when doing recursion. After looking at a few solutions, here's the code I have in Javascript:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    return treeHeight(root) !== -1;
};

function treeHeight(root){
    if(!root) return 0;
    const leftSubTree = treeHeight(root.left);
    const rightSubTree = treeHeight(root.right);
    if(leftSubTree === -1 || rightSubTree === -1) return -1; // how can recursion lead to either subtree being -1? At this point I don't know how this can be true other than "that's just how recursion works"
    if(Math.abs(leftSubTree - rightSubTree) > 1) return -1; // how are the values of either subtree even obtained here?
    return Math.max(leftSubTree, rightSubTree) + 1; // same as the previous question. how do either subtree even get values?
}

I'm trying to understand the following lines:

    if(leftSubTree === -1 || rightSubTree === -1) return -1; // how can recursion lead to either subtree being -1? At this point I don't know how this can be true other than "that's just how recursion works"
    if(Math.abs(leftSubTree - rightSubTree) > 1) return -1; // how are the values of either subtree even obtained here?
    return Math.max(leftSubTree, rightSubTree) + 1; // same as the previous question. how do either subtree even get values?

I get that the recursion will traverse down the tree on the left side and the rightside. I don't get how through recursion, the subtrees values are getting computed. Can someone explain it please?

Have you tried stepping through it in a debugger? Or execute it by hand on paper. That's the best way to learn how things like this work. — Barmar
– Barmar, Commented Oct 19, 2022 at 21:05
@Barmar Cannot debug in Leetcode. I can only do console logging but it is giving several values separated by newline char. I don't know how the value is even getting computed. It isn't clear so I wouldn't know what to write on paper. For example, let's say the leftSubTree gets computed to be 5 (just an example), I don't know how to explain how 5 got there. I just know once base case of root being null returns 0, that the recursion would stop. I don't know how to write on paper how the values are getting computed to become 5. Can you help or show me where I can find out? — Bmoe
– Bmoe, Commented Oct 19, 2022 at 21:09
It gets there by calling the function again, with root.left as the argument. It keeps recursing until it gets to a leaf where the value is null. — Barmar
– Barmar, Commented Oct 19, 2022 at 21:10
@Barmar Yes I get that, but how does it know what value to return for each recursive call? — Bmoe
– Bmoe, Commented Oct 19, 2022 at 21:11
Like look at left subtree for example: treeHeight(root.left). What value is getting computed at each recursive call? I only know the last call will be 0 because that is the base case. How are the rest of the values getting computed? — Bmoe
– Bmoe, Commented Oct 19, 2022 at 21:12

Jagrut Sharma · Accepted Answer · 2022-10-19 21:43:01Z

1

I drew this diagram that may help you visualize. When the recursion unfolds, the values passed to parent are underlined in red color. Each node will check the difference of the values reported by its left and right child. If at any node, the diff is > 1, it is not balanced.

Also, at each node, it takes the max of the values reported by left and right child, adds 1 to it (for current level) and sends to its parent.

The left tree is balanced, and the right is not.

edited Oct 19, 2022 at 21:43

answered Oct 19, 2022 at 21:33

Jagrut Sharma

4,7843 gold badges17 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

IT goldman · Accepted Answer · 2022-10-19 21:16:49Z

0

few things to note:

a tree height is the deepest level to its leaf.
naturally, a parent height is the height of its tallest child +1.
a tree is balanced if the difference between ALL its children heights is 1 or less.
the function name treeHeight is confusing. should be called balancedTreeHeightOrMinusOne

so a tree is balanced if balancedTreeHeightOrMinusOne is not -1; it is calculated by checking (recursively) the balancedTreeHeightOrMinusOne of its children. if the diff between them is too big then return -1 for this is not balanced. Otherwise return the height of it's tallest children plus one.

answered Oct 19, 2022 at 21:16

IT goldman

20.4k2 gold badges18 silver badges34 bronze badges

Comments

trincot · Accepted Answer · 2022-10-19 21:17:11Z

The base case is this:

if(!root) return 0;

So we know how the function could return 0.

The next case to look at is this one:

return Math.max(leftSubTree, rightSubTree) + 1;

We know from the base case that both leftSubTree and rightSubTree could be 0 (since they represent a return value from a recursive call), and so we then have a case here where 1 is returned. So now we have seen that either 0 or 1 could be returned.

But then this return could also get a maximum that is 1, and so return 2! And so any positive integer becomes a possible return value.

Now look at this statement:

if(Math.abs(leftSubTree - rightSubTree) > 1) return -1;

As we saw that leftSubTree and rightSubTree could be any unsigned integer (since they are the values returned by a recursive call), the absolute difference can be any unsigned integer, and so there can be cases where this condition is true. So now we have a first case where the returned value is -1 (which here means: "it is not balanced").

The only statement that remains to be explained:

if(leftSubTree === -1 || rightSubTree === -1) return -1;

In the previous case we saw that indeed a recursive call can return -1. So here it says that if either subtree is not balanced then this tree is not balanced either.

Barmar · Accepted Answer · 2022-10-19 21:18:07Z

Suppose you have a simple tree like:

const tree = {
  val: 1,
  left: null,
  right: {
    val: 2,
    left: null,
    right: null
  }
}

When you call treeHeight(tree), you get two recursive calls: treeHeight(tree.left) and treeHeight(tree.right).

Since tree.left is null, treeHeight(tree.left) returns 0, so leftSubtree == 0.

tree.right is not null, so it recurses again, calling treeHeight(tree.right.left and treeHeight(tree.right.right). Since both of these are null, both return values are 0, so in this call, leftSubtree == 0 and rightSubtree == 0. Math.abs(leftSubTree - rightSubTree) == 0, so it returns Math.max(leftSubtree, rightSubtree) + 1. Since Math.max(0, 0) is 0, this returns 1.

So in the original call, we now have rightSubtree == 1. Math.abs(leftSubTree - rightSubTree) > 1) == 1, so the condition Math.abs(leftSubTree - rightSubTree) > 1) fails. We go to the else block and return Math.max(leftSubtree, rightSubtree) + 1. This returns 2.

Collectives™ on Stack Overflow

How is Recursion Populating SubTree Values in Binary Tree?

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related