Why the java.lang.StackOverflowError happened?


  • 1
    A
    public boolean isBalanced(TreeNode root) {
        if (root ==null) {
            return true;
        } else if (!isBalanced(root.left) || !isBalanced(root.right) ) {
            return false;
        } else {
            return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1;
        }
    }
    
    
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
    

    }


  • 0
    M

    Because each recursive call uses some space on the stack. If your recursion is too deep, then it will result in StackOverflow, depending upon the maximum allowed depth in the stack.

    If you trace your code, you are doing two recursions starting from each node till the last level. This problem can be solved using single recursion visiting a node only once.

    The guy who set this problem designed a test case like below, which is clearly a binary tree with 'n' nodes and 'n' levels. Just think of the memory overhead that is caused by your code.

    [0,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]


  • 1

    @mandalapusc.edu said in Why the java.lang.StackOverflowError happened?:

    If you trace your code, you are doing two recursions starting from each node till the last level. This problem can be solved using single recursion visiting a node only once.

    They're done one after the other, from the same stack level, no? So that sounds like a time thing, not like a stack space thing.

    Interestingly, it gets accepted if you just store the left and right maxDepth in variables and take the max of those:

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
    

    Not sure why... I think that's pretty much what the original version would do as well - get the two maxDepths and store them somewhere and then call the max function with the two results. Maybe they're stored on the stack while my explicit variables aren't? Strange.

    This works as well:

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int right = maxDepth(root.right);
        return Math.max(maxDepth(root.left), right) + 1;
    }

  • 0
    M

    @StefanPochmann It's strange but interesting. Some nice observations are made by you. Yeah, It is one after the other. My explanation was not clear on that. I believe the stack space is cleaned up once we assign the return value to a variable but not sure if it does or doesn't follow the same if we do not use any variable.


  • 1

    I did some more experiments to find out the maximum depth the functions can handle:

    • @ainiyouyou's original breaks somewhere between 12000 and 13000 nodes.
    • My two-variable version breaks somewhere between 14000 and 15000 nodes.
    • My one-variable version breaks somewhere between 16000 and 17000 nodes. Huh?!

    The code:

    public class Solution {
        public boolean isBalanced(TreeNode root) {
            root = null;
            for (int i=0; i<12000; i++) {
                TreeNode tmp = new TreeNode(0);
                tmp.left = root;
                root = tmp;
            }
            System.out.println(maxDepth1(root));
            return true;
        }
        
        public int maxDepth1(TreeNode root) {
            if (root == null) return 0;
            return Math.max(maxDepth1(root.left), maxDepth1(root.right)) + 1;
        }
    
        public int maxDepth2(TreeNode root) {
            if (root == null) return 0;
            int left = maxDepth2(root.left);
            int right = maxDepth2(root.right);
            return Math.max(left, right) + 1;
        }
    
        public int maxDepth3(TreeNode root) {
            if (root == null) return 0;
            int right = maxDepth3(root.right);
            return Math.max(maxDepth3(root.left), right) + 1;
        }
    }
    

    I also tried finding the breaking points programmatically (binary or linear search), but the JVM seems to somehow adapt and allow deeper recursion in later calls. So I ended up using just one call and submitting (with "Run Code", I mean) my code several times with different numbers.

    Still don't know why they differ...


Log in to reply
 

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