Why the java.lang.StackOverflowError happened?

• ``````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;
}
``````

}

• 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]

• @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;
}``````

• @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.

• 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...

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