LeetCode — Balanced Binary Tree

Problem Link: https://leetcode.com/problems/balanced-binary-tree/

Problem Description: Given a binary tree, determine if it is height-balanced.

binary tree

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -104 <= Node.val <= 104

Approach Used: Recursion

Explanation: Definition of a height-balanced tree is: a binary tree in which the left and right subtrees of every node differ in height by no more than 1. So to find out if the tree is balanced or not we just need to find for every node the height of its left sub-tree and right sub-tree. If the absolute difference between their height is less than equal 1, then we recursively check whether the left and right subtrees are themselves balanced or not. It all conditions satisfy then we say that the subtree rooted with the current node is balanced. If the current node is the root node of the tree then the whole tree is height-balanced.

To find the height of tree: We find the height of its left and right subtree and then the height of this tree will be 1 + max(left tree height, right tree height). The base case is when the current node is null in that case the height will be 0.

Code: (Java)

//function to calculate height
 public int findHeight(TreeNode root){
 // height will be 0 if there is no node
 if(root==null)
 return 0;
 
 //find height of left-subtree
 int lHeight = findHeight(root.left);
 //find height of right-subtree
 int rHeight = findHeight(root.right);
 
 //height of tree with current node as root will be max(left, right)+1
 return 1+Math.max(lHeight, rHeight);
 }
 public boolean isBalanced(TreeNode root) {
 //if no node present, then tree is always balanced (Base case)
 if(root==null)
 return true;
 
 //finding Height of subtrees based on above defined function
 int lHeight= findHeight(root.left);
 int rHeight= findHeight(root.right);
 
 //if current node is balanced and both its subtrees are balanced
 if(Math.abs(lHeight-rHeight)<=1 && isBalanced(root.left) && isBalanced(root.right))
 return true;
 //if any of the above condition is violated
 return false;
 }

Code: (Java — Optimised):

Although the above code gets accepted on Leetcode, it calculates height at each node several times which is not preferred for a tree with a very large number of nodes. At each node, we should use the information sent by its children. So if we find that the current node is unbalanced, we send that info (by sending height as -1) to its parent so that it doesn't further calculate any height.

//function to calculate height
 public int findHeight(TreeNode root){
 // height will be 0 if there is no node
 if(root==null)
 return 0;
 
 //recursively find height of left-subtree
 int lHeight = findHeight(root.left);
 //if left subtree is unbalanced then no need to calculate further.
 if(lHeight==-1)
 return -1;
 //recursively find height of right-subtree
 int rHeight = findHeight(root.right);
 //if right subtree is unbalanced then no need to calculate further.
 if(rHeight==-1)
 return -1;
 
 //if current tree is unbalanced then we return -1
 if(Math.abs(lHeight-rHeight)>1)
 return -1;
 
 //height of tree with current node as root will be max(left, right)+1
 return 1+Math.max(lHeight, rHeight);
 }
 public boolean isBalanced(TreeNode root) {
 //if no node present, then tree is always balanced (Base case)
 if(root==null)
 return true;
 
 //if unbalanced node is encountered while finding height of root node
 if(findHeight(root)==-1)
 return false;
 
 return true;
 
 }

Complexity:

Space complexity: O(n). Internal stack space used for recursive calls to left and right sub-trees.

Time complexity: O(n). Visiting each node exactly once while calculating height.