• 2

Check binary tree balanced or not
  • Posted: 5 years ago
  • Updated: 2 years ago
  • Edit
  • answers (3)
  • views (19884)

Suppose you are given a binary tree. Write a function to check whether the tree is balanced or not.


Posted Answers

  • Posted: 2 years ago
  • Updated: 2 years ago
  • 0 0
  • Edit

 
class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}
static Hashtable  haTab = new Hashtable ();

	static int height(TreeNode root) {
		// if the node is null then it returns the height as -1
		int heightOfNode;
		if (root == null) {
			return -1;
		}
		if (haTab.containsKey(root)) {
			return haTab.get(root);
		}
		int leftHeight, rightHeight;
		leftHeight = height(root.left);
		rightHeight = height(root.right);
		// finds the height of left subtree and right subtree and returns
		// the max of both + 1
		heightOfNode = Math.max(leftHeight, rightHeight) + 1;
		haTab.put(root, heightOfNode);
		return heightOfNode;
	}
public static boolean isBalanced(TreeNode root) {
		if (root == null) {
			return true;
		}
		int leftHeight, rightHeight;
		leftHeight = height(root.left);
		rightHeight = height(root.right);
		// if left child and right child are balanced and the difference in
		// their heights is  <  2
		// then it is balanced
		if (isBalanced(root.left)  & &  isBalanced(root.right)
				 & &  Math.abs(leftHeight - rightHeight)  <  2) {
			return true;
		}
		return false;
	}
public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(-2);
		root.right = new TreeNode(-3);
		root.left.left = new TreeNode(1);
		root.left.right = new TreeNode(3);
		root.right.right = new TreeNode(-1);
		System.out.println(hasPathSum(root, -1));
	}
  • Posted: 2 years ago
  • Updated: 2 years ago
  • 0 0
  • Edit

 
class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}
static Hashtable  haTab = new Hashtable ();

	static int height(TreeNode root) {
		// if the node is null then it returns the height as -1
		int heightOfNode;
		if (root == null) {
			return -1;
		}
		if (haTab.containsKey(root)) {
			return haTab.get(root);
		}
		int leftHeight, rightHeight;
		leftHeight = height(root.left);
		rightHeight = height(root.right);
		// finds the height of left subtree and right subtree and returns
		// the max of both + 1
		heightOfNode = Math.max(leftHeight, rightHeight) + 1;
		haTab.put(root, heightOfNode);
		return heightOfNode;
	}
public static boolean isBalanced(TreeNode root) {
		if (root == null) {
			return true;
		}
		int leftHeight, rightHeight;
		leftHeight = height(root.left);
		rightHeight = height(root.right);
		// if left child and right child are balanced and the difference in
		// their heights is  <  2
		// then it is balanced
		if (isBalanced(root.left)  & &  isBalanced(root.right)
				 & &  Math.abs(leftHeight - rightHeight)  <  2) {
			return true;
		}
		return false;
	}
public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(-2);
		root.right = new TreeNode(-3);
		root.left.left = new TreeNode(1);
		root.left.right = new TreeNode(3);
		root.right.right = new TreeNode(-1);
		System.out.println(hasPathSum(root, -1));
	}
  • Posted: 5 years ago
  • Updated: 5 years ago
  • 2 0
  • Edit

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.

< Polynomial time algorithm >


  • Take the root. Compute the height of its left and right sub tree.
  • If the difference between height of the left and right sub tree is less than or equal to \( 1 \), return true.
  • Otherwise, return false.
  • Repeat these two steps for each node in the given binary tree.

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.

 
public static boolean checkBinaryTreeIsBalanced(TreeNode root){

     /* Base case - Empty tree is always balanced */
     if(root == null)
          return true;

     /* Compute height of the left and right subtree and their difference */
    int heightDifference = computeHeight(root.left) - computeHeight(root.right);

    if(Math.abs(heightDifference)  < = 1)
          return checkBinaryTreeIsBalanced(root.left)  & & 
                 checkBinaryTreeIsBalanced(root.right);
    else
          return false;
    
 }

public int computeHeight(TreeNode root){

      /* Base case - Tree is empty */
      if(root == null)
           return 0;
      /* Calculate recursively */
      return Math.max(computeHeight(root.left), computeHeight(root.right)) + 1;
 }


< 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){

     if(computeAndCheckHeight(root) == -1)
          return false;
     else
          return true;
 }

public int computeAndCheckHeight(TreeNode root){
     /* Base case - Tree is empty */
     if(root == null)
          return 0;
     /* Height of left subtree */
     int leftSubTreeHeight = computeAndCheckHeight(root.left);
     /* Left subtree is not balanced */
     if(leftSubTreeHeight == -1)
          return -1;  

     /* Height of right subtree */
     int rightSubTreeHeight = computeAndCheckHeight(root.right);
     /* Right subtree is not balanced */
     if(rightSubTreeHeight == -1)
          return -1;

     /* Difference in height */
     int heightDifference = Math.abs(leftSubTreeHeight - rightSubTreeHeight);
     /* Root node is not balanced */
     if(heightDifference > 1)
          return -1;
     else
          /* Height of the root node */
          return Math.max(leftSubTreeHeight, rightSubTreeHeight) + 1;
 }

Time complexity = \( O(n) \).

You need to Sign In to post your solution.