Given a binary tree, determine if it is height-balanced.
A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
The solution presented is a recursive. Find the height of left and right subtrees and check the difference of the heights. If the difference is more than 1 the tree is not balanced. The tree is balanced if the difference is zero or one.
Implementation:
public class CrazyforCode { public boolean isBalanced(TreeNode root) { int left,right; if(root ==null){ return true;} left = getHeight(root.left); right =getHeight(root.right); return (Math.abs(left-right)<=1 && isBalanced(root.left) && isBalanced(root.right)); } public int getHeight(TreeNode root){ if(root ==null) return 0; int left = getHeight(root.left); int right = getHeight(root.right); return 1+ (left>right?left:right); } }
Nice solution, but space complexity will be O(H) where H is the height of the tree. This is because stack allocation for recursion.
Should we consider stack allocation of recursion for space complexity.we are not allocating any space right