leetcode 110. Balanced Binary Tree，Problems with balanced tree code

Question

I am working on LeetCode problem 110. Balanced Binary Tree:

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

I've seen solutions for this question, including this one:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int max(int a, int b){
    return (a > b) ? a:b;
}
int height(struct TreeNode* root){
    if(root == NULL) return 0;
    return 1 + max(height(root->left),height(root->right));
}
bool isBalanced(struct TreeNode* root){
    if(root == NULL) return 1;
    int left = height(root->left);
    int right = height(root->right);
    
    return abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}

My question is: why should this code be added?

isBalanced(root->left) && isBalanced(root->right);

It seems to be working fine when I delete this from the code. However, when the test case is [1,2,2,3,null,null,3,4,null,null,4], the code will return true, while the expected answer is false.

I am full of doubts about this test, because both ends of the test tree are the same depth, so abs(left-right) should be 0, and 0<=1, so shouldn't the answer for this test be true!?

I think you are correct in this assessment.

Daniel Hao
– Daniel Hao

2022-01-24 02:14:14 +00:00
Commented Jan 24, 2022 at 2:14 — Daniel Hao
– Daniel Hao, Commented Jan 24, 2022 at 2:14

trincot · Accepted Answer · 2022-01-25 18:52:57Z

the test case is [1,2,2,3,null,null,3,4,null,null,4],

So let's visualise that tree:

            1
           / \
          2   2
         /     \
        3       3
       /         \
      4           4

the code will return true, while the expected answer is false,

The expected answer is false: the above tree is not a balanced tree.

I am full of doubts about this test, because both ends of the test tree are the same depth, so abs(left-right) should be 0, and 0<=1, so shouldn't the answer for this test be true!?

You are right that abs(left-right) is 0 and that's within the bounds [-1,1], but in a balanced tree, this condition must be true in every node. So your code must also check that abs(left-right) is within the limits for other nodes. And then you can see that the first node with value 2, has a left-subtree that is 2 levels higher than its right-subtree (which is empty). So there we have a violation of the rule, and the correct answer is false.

This explains why you really need those two recursive calls to isBalanced.

rubenskx · Accepted Answer · 2022-02-19 20:23:02Z

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Here you have already mentioned why your implementation is throwing up an error. Your code only checks the height balancing at the root node(topmost node).

The difference of heights in every node must be [-1,0,1] in a balanced tree. An easier visualization will be considering each node has a small tree itself.

Let this be the testcase [1,2,2,3,null,null,3,4,null,null,4].

       1
      / \
     2   2
    /     \
   3       3
  /         \
 4           4

If you only check the root node, the abs(left-right) is 0. But consider the left node 2. And visualize it a smaller tree or a subtree.

If this is a tree on its own then it's not balanced since abs(left-right) == 2.Since we have found a node that is not balanced we return false.

Thus to solve this problem, we have to consider each node as a separate tree itself. Such problems require recursive algorithms that checks the isBalanced property from the highest to the lowest nodes by calling their child nodes recursively.

Collectives™ on Stack Overflow

leetcode 110. Balanced Binary Tree，Problems with balanced tree code

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related