Balanced Binary Tree LeetCode

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

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

 Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Constraints:

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

This problem is popular in LeetCode. A collection of hundreds of interview questions and solutions are available in our blog at Interview Question

Solution

	package com.alg.leetcode;
	/**
	* Given a binary tree, determine if it is height-balanced.
	For this problem, 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.
	*
	* Solution 1:
	* 1)handle base case, if the root node is null then return true
	* 2) compute the height of the left node and the right node
	* 2 a) if the height diff is more than 1 return false
	* 2 b) repeat 2 until the node is null
	* 3) to compute the height
	* 3 a) if the node is null, return 0
	* 3 b) else return 1 + max(height of left, height of right)
	*
	Complexity: O(n^2) when the tree is skewed, if the tree is balanced then it is more likely O(height of tree)
	*
	* Solution 2: compute the height while we are checking if the tree is balanced
	*
	*
	*
	*
	* @author rbaral
	*/
	public class BalancedBinaryTree {
	public static boolean isBalanced(TreeNode root){
	if(heightDiff(root)==-1){
	return false;
	}else{
	return true;
	}
	}
	//we return -1 to wait for the right subtree to be computed
	static int heightDiff(TreeNode root){
	if(root ==null){
	return 0;
	}
	int leftTreeHeight = heightDiff(root.left);
	if(leftTreeHeight==-1){
	return -1;
	}
	int rightTreeHeight = heightDiff(root.right);
	if(rightTreeHeight==-1){
	return -1;
	}
	int heightDiff = Math.abs(leftTreeHeight - rightTreeHeight);
	if(heightDiff>1){
	return -1;
	}else{
	return 1 +Math.max(leftTreeHeight, rightTreeHeight);
	}
	}
	public static boolean isBalanced1(TreeNode root) {
	if(root==null){
	return true;
	}else{
	int heightDiff = getHeight(root.left) - getHeight(root.right);
	if (Math.abs(heightDiff)>1){
	return false;
	}else{
	return isBalanced1(root.left) && isBalanced1(root.right);
	}
	}
	}
	static int getHeight(TreeNode root){
	if(root==null){
	return 0;
	}else{
	return 1 + Math.max(getHeight(root.left), getHeight(root.right));
	}
	}
	public static void main(String args[]){
	}
	}

view raw BalancedBinaryTree.java hosted with ❤ by GitHub