The bottom up O(N) solution would be better


  • 310
    B

    This problem is generally believed to have two solutions: the top down approach and the bottom up way.

    1.The first method checks whether the tree is balanced strictly according to the definition of balanced binary tree: the difference between the heights of the two sub trees are not bigger than 1, and both the left sub tree and right sub tree are also balanced. With the helper function depth(), we could easily write the code;

    class solution {
    public:
        int depth (TreeNode *root) {
            if (root == NULL) return 0;
            return max (depth(root -> left), depth (root -> right)) + 1;
        }
    
        bool isBalanced (TreeNode *root) {
            if (root == NULL) return true;
            
            int left=depth(root->left);
            int right=depth(root->right);
            
            return abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right);
        }
    };
    

    For the current node root, calling depth() for its left and right children actually has to access all of its children, thus the complexity is O(N). We do this for each node in the tree, so the overall complexity of isBalanced will be O(N^2). This is a top down approach.

    2.The second method is based on DFS. Instead of calling depth() explicitly for each child node, we return the height of the current node in DFS recursion. When the sub tree of the current node (inclusive) is balanced, the function dfsHeight() returns a non-negative value as the height. Otherwise -1 is returned. According to the leftHeight and rightHeight of the two children, the parent node could check if the sub tree
    is balanced, and decides its return value.

    class solution {
    public:
    int dfsHeight (TreeNode *root) {
            if (root == NULL) return 0;
            
            int leftHeight = dfsHeight (root -> left);
            if (leftHeight == -1) return -1;
            int rightHeight = dfsHeight (root -> right);
            if (rightHeight == -1) return -1;
            
            if (abs(leftHeight - rightHeight) > 1)  return -1;
            return max (leftHeight, rightHeight) + 1;
        }
        bool isBalanced(TreeNode *root) {
            return dfsHeight (root) != -1;
        }
    };
    

    In this bottom up approach, each node in the tree only need to be accessed once. Thus the time complexity is O(N), better than the first solution.


  • 77
    S

    Great post. though I would argue that the first approach is O(NlogN)

    for each level you are doing a total scan of N, and there are logN levels.


  • 17
    N

    if the tree is skewed binary tree(just a linked list ), the first approach would be O(N2)
    so the worst case is O(N2). Am I right?


  • 0
    J

    Great work,thanks


  • 0
    A

    Brilliant solution, very well thought ,thank you :)


  • 0
    B

    Yeah, that's what I have in mind.


  • 0
    B

    thanks for your reading!


  • 6
    V

    If the tree was skewed, then the first "abs" condition will fail and we wont proceed further for root->left and root->right


  • 1
    Q

    (just fixed the error in early code, as @prime_tang commented out)

    thanks, below is of the same idea, just 2 less return statements

    class Solution {
        int depth_Plus_One(TreeNode *root) {
        // return depth+1 if balanced, else 0
            if(!root) return 1;
            int ld=depth_Plus_One(root->left);
            if(ld) {
                int rd=depth_Plus_One(root->right);
                if(rd && std::abs(ld-rd)<2) {
                    return 1+std::max(ld,rd);
                }
            }
            return 0;
        }
    public:
        bool isBalanced(TreeNode* root) {
            return 0 != depth_Plus_One(root);
        }
    };
    

  • 0
    S

    brilliant solution!
    but I have a question, on the first approach can you explain why we need to check isbalanced(root->left) and isbalanced(root->right) at the end ?


  • 0

    Hi, @syjohnson. We need to check isBalanced(root -> left) and isBalanced(root -> right) because that's the definition of balancedness: the depth difference between the left and right subtrees is not larger than 1 and both the left and right subtrees are itself balanecd.


  • 0

    I guess @venkata_sundara is correct.


  • 0

    @qeatzy's code is not a good solution, if ld < 0, no need to calculate rd, we should judge immediately after int ld=balanceness(root->left);


  • 0
    S
    This post is deleted!

  • 2

    Hey guys, I implemented the two methods in Java but found the O(N^2) one costs 2ms and the O(N) one costs 22 ms. :( Cound anybody help find out why?

    Here is my Java code.

    The O(N^2) code:

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(Height(root.left) - Height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    
    public int Height(TreeNode root) {
        if (root == null)
            return 0;
        return Math.max(Height(root.left), Height(root.right)) + 1;
    }
    

    The O(N) code:

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return dfsHeight(root) != -1;
    }
    
    public int dfsHeight(TreeNode root) {
        if (root == null)
            return 0;
        int leftHeight = dfsHeight(root.left);
        if (leftHeight == -1) return -1;
        int rightHeight = dfsHeight(root.right);
        if (rightHeight == -1) return -1;
        if (Math.abs(leftHeight - rightHeight) > 1)
            return -1;
        return Math.max(dfsHeight(root.left), dfsHeight(root.right)) + 1;
    }
    

  • 9
    M

    Because your last sentence in dfsHeight(TreeNode root) that's return Math.max(dfsHeight(root.left), dfsHeight(root.right)) + 1; should be return Math.max(leftHeight,rightHeight)+1;


  • 2

    @annitqt As what @wenzhong003 suggests, you repeatedly called dfsHeight(root.left) and dfsHeight(root.right) in the last line of dfsHeight. But these results have been saved in leftHeight and rightHeight. So you are repeatedly doing unnecessary things and so they take you more time.


  • 0
    B
    This post is deleted!

  • 0
    C

    brilliant summary and explanation


  • 16
    V

    Another way of proving the time complexity of first approach is O(nlogn) using Master Theory:

    Time complexity for depth:

    T(n) = 2T(n/2) + O(1)

    a = 2, b =2, d = 0

    a > b^d, therefore, O(n^(logba)) = O(n)

    Time complexity for isBalanced:

    T(n) = 2T(n/2) + O(n)

    a = 2, b =2, d = 1

    a = b^d, therefore, O(n^d*logn) = O(nlogn)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.