Simple Java Recursive Solution O(nlogn)


  • 2
    I
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public boolean isBalanced(TreeNode root) {
            if(null == root) {
                return true;
            }
            
            return Math.abs(height(root.left) - height(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right);
        }
        
        public int height(TreeNode root) {
            if(null == root) {
                return 0;
            }
            
            return 1 + Math.max(height(root.left), height(root.right));
        }
    }
    

  • 0
    F

    Can you please explain why the time complexity is O(nlogn) ? Thanks.


  • 0
    I

    My understanding is that for every node (n nodes) you do height (O(log(n))) consequently O(nlog(n))


  • 0
    J

    I don't think time complexity is right.
    This is my solution .
    In first level, O(1) time to split T(n) to 2T(n/2)
    second level, O(2) time to split 2
    T(n/2) to 4*(n/4)
    Thus, time complexity is O(n).

    public class Solution {
        public boolean isBalanced(TreeNode root) {
            int res = helper(root);
            return res != -1;
        }
        
        private int helper(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = helper(root.left);
            int right = helper(root.right);
            if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
                return -1;
            }
            return Math.max(left, right) + 1;
        }
    }
    

  • 0
    Y

    Complexity of Height() when called on a tree with 'n' nodes is O(n). (It visits every node once)
    As we descend each level, Height() is called on subtrees with only n/2 nodes.

    Lets take a complete binary tree,
    When isBalanced() calls Height() on the root node -> n
    When called from level 2 -> n/2 + n/2
    When called from level 3 -> n/4 + n/4 + n/4 + n/4
    ......
    When called from last level -> again n (n/L x L times)

    So total complexity = n * no.of levels = O(nlogn)

    PS: Just edit Height Function to remember when height difference of Child Subtrees > 1 for a O(n) solution.


Log in to reply
 

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