Suppose you are given a binary tree. Write a function to check whether the tree is balanced or not.
|
|
A binary tree is balanced when the depth (from the root) of the left and right sub trees of every node differs by \( 1 \) or less. We can check whether a binary tree is balanced or not using recursion.
Worst case time complexity for skewed binary tree is \( O(n^{2}) \). In that case, the height of the tree is \( \theta(n) \) and at each level the height is computed which takes \( O(n) \) time. < Linear time algorithm > We can optimize the above algorithm and solve the problem in linear time. Instead of computing the height at each level, we can compute it in the same recursion. public static boolean checkBinaryTreeIsBalanced(TreeNode root){ Time complexity = \( O(n) \). |