Balanced Binary Tree Editorial

Practice Problem Link: Balanced Binary Tree

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

A binary tree is considered balanced if the difference between the heights of the left and the right subtree is not more than 1 for any given node.

Given the root node of a binary tree, determine whether it's height-balanced.

Naive Approach

The idea is to check the difference between the heights/depths of the left and right subtree for every node in the tree. If for any node the difference is greater than 1 then return false otherwise return true.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
int getDepth(Node *root) {
	if(root == NULL) {
		return 0;
	}
	int leftSubtreeDepth = getDepth(root->left);
	int rightSubtreeDepth = getDepth(root->right);
	return max(leftSubtreeDepth, rightSubtreeDepth) + 1;
}
bool isBinaryTreeBalanced(Node* root) {
    if (root == NULL) {
		return true;
	}
	int leftSubtreeDepth = getDepth(root->left);
	int rightSubtreeDepth = getDepth(root->right);
	if(abs(leftSubtreeDepth - rightSubtreeDepth) <= 1 && isBinaryTreeBalanced(root->left) && isBinaryTreeBalanced(root->right)) {
		return true;
	}
	return false;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	int getDepth(Node root) {
		if(root == null) {
			return 0;
		}
		int leftSubtreeDepth = getDepth(root.left);
		int rightSubtreeDepth = getDepth(root.right);
		return Math.max(leftSubtreeDepth, rightSubtreeDepth) + 1;
	}
	boolean isBinaryTreeBalanced(Node root) {
	    if (root == null) {
			return true;
		}
		int leftSubtreeDepth = getDepth(root.left);
		int rightSubtreeDepth = getDepth(root.right);
		if(Math.abs(leftSubtreeDepth - rightSubtreeDepth) <= 1 && isBinaryTreeBalanced(root.left) && isBinaryTreeBalanced(root.right)) {
			return true;
		}
		return false;
	}
}

Optimal Approach

The optimal approach is exactly the same as the naive approach but the calculation of heights of the subtree and checking the height difference between the two subtrees of a node is done simultaneously in a single function to optimize the time complexity.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
int getDepth(Node *root, bool &isBalanced) {
	if(root == NULL) {
		return 0;
	}
	int leftSubtreeDepth = getDepth(root->left, isBalanced);
	int rightSubtreeDepth = getDepth(root->right, isBalanced);
	if(abs(leftSubtreeDepth - rightSubtreeDepth) > 1) {
		isBalanced = false;
	}
	return max(leftSubtreeDepth, rightSubtreeDepth) + 1;
}
bool isBinaryTreeBalanced(Node* root) {
    bool isBalanced = true;
	getDepth(root, isBalanced);
	return isBalanced;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	static boolean isBalanced;
	int getDepth(Node root) {
		if(root == null) {
			return 0;
		}
		int leftSubtreeDepth = getDepth(root.left);
		int rightSubtreeDepth = getDepth(root.right);
		if(Math.abs(leftSubtreeDepth - rightSubtreeDepth) > 1) {
			isBalanced = false;
		}
		return Math.max(leftSubtreeDepth, rightSubtreeDepth) + 1;
	}
	boolean isBinaryTreeBalanced(Node root) {
	    isBalanced = true;
		getDepth(root);
		return isBalanced;
	}
}