Solution For Balanced Binary Tree
The Balanced Binary Tree problem on LeetCode can be found at https://leetcode.com/problems/balanced-binary-tree/.
The problem statement is as follows:
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.
To solve this problem, we need to recursively check the height of the left and right subtrees of each node and compare them. If the difference between the heights is greater than 1, then the tree is not height-balanced.
We will implement a recursive solution to check the height of the tree and compare the heights of the left and right subtrees.
First, we will define a helper function to calculate the height of a given node:
int height(TreeNode* node) {
if (!node) {
return 0;
}
return 1 + max(height(node->left), height(node->right));
}
The height
function takes a node as input and recursively calculates the height of the subtree rooted at that node. If the node is NULL
, the function returns 0. Otherwise, it returns 1 plus the maximum height of the left and right subtrees.
Next, we will define the main function isBalanced
which takes the root of the binary tree as input:
bool isBalanced(TreeNode* root) {
if (!root) {
return true;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}
The isBalanced
function first checks if the root is NULL
. If it is NULL
, the function returns true
because an empty tree is always height-balanced.
If the root is not NULL
, we calculate the height of the left and right subtrees using the height
function. We then check if the absolute difference between the heights is greater than 1. If it is, the function returns false
because the tree is not height-balanced.
If the difference between the heights is less than or equal to 1, we recursively call isBalanced
on the left and right subtrees. If both subtrees are height-balanced, the function returns true
. Otherwise, if either subtree is not height-balanced, the function returns false
.
The time complexity of this solution is O(n^2) in the worst case because we may need to calculate the height of each node in the binary tree, and each height calculation takes O(n) time in the worst case. The space complexity is O(n) because we use recursion to traverse the binary tree and store the maximum height of each subtree on the call stack.
However, we can optimize the time complexity to O(n) by calculating the height of each node only once. We can do this by modifying the height
function to check if the subtree rooted at a node is height-balanced and return the height of the subtree at the same time. This avoids redundant calculations of the subtree height.
Here is the optimized height
function:
int height(TreeNode* node, bool& balanced) {
if (!node) {
return 0;
}
int leftHeight = height(node->left, balanced);
int rightHeight = height(node->right, balanced);
if (abs(leftHeight - rightHeight) > 1) {
balanced = false;
}
return 1 + max(leftHeight, rightHeight);
}
We add a boolean parameter balanced
to the height
function to indicate if the subtree rooted at a node is height-balanced. If the difference between the heights of the left and right subtrees is greater than 1, we set balanced
to false
.
Here is the modified isBalanced
function using the optimized height
function:
bool isBalanced(TreeNode* root) {
bool balanced = true;
height(root, balanced);
return balanced;
}
The isBalanced
function initializes balanced
to true
and calls the height
function on the root. The function then returns the value of balanced
.
With the optimized height
function, the time complexity of this solution is O(n) in the worst case, and the space complexity is O(n) due to the recursion.
Step by Step Implementation For Balanced Binary Tree
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isBalanced(TreeNode root) { //check if tree is empty if(root == null) return true; //get the height of left and right sub-trees int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); //check if the difference in height of left and right sub-trees is not more than 1 and //that the left and right sub-trees are balanced return (Math.abs(leftHeight - rightHeight) <= 1) && isBalanced(root.left) && isBalanced(root.right); } //function to get the height of a tree public int getHeight(TreeNode root){ //check if tree is empty if(root == null) return 0; //if tree is not empty, return the height of the tree by recursively //calculating the height of the left and right sub-trees return 1 + Math.max(getHeight(root.left), getHeight(root.right)); } }
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def isBalanced(self, root: TreeNode) -> bool: # A tree is balanced if the difference in the depths # of its left and right subtrees is not more than 1. # An empty tree is balanced. # Return True if the tree is balanced, False otherwise. if not root: return True return (abs(self.depth(root.left) - self.depth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)) def depth(self, root): # Return the depth of the tree. if not root: return 0 return 1 + max(self.depth(root.left), self.depth(root.right))
var isBalanced = function(root) { if (!root) return true; function getHeight(node) { if (!node) return 0; return 1 + Math.max(getHeight(node.left), getHeight(node.right)); } return Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); };
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isBalanced(TreeNode* root) { // An empty tree is balanced by definition if (root == nullptr) { return true; } // Check if the subtrees are balanced, and if the // difference in their heights is no more than 1. return isBalanced(root->left) && isBalanced(root->right) && abs(getHeight(root->left) - getHeight(root->right)) <= 1; } int getHeight(TreeNode* root) { // An empty tree has height -1 if (root == nullptr) { return -1; } // The height of a tree is the maximum height of its subtrees // plus 1 (for the root node). return 1 + max(getHeight(root->left), getHeight(root->right)); } };
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { public bool IsBalanced(TreeNode root) { // Base case if (root == null) { return true; } // Recursive case int heightDiff = GetHeight(root.left) - GetHeight(root.right); if (Math.Abs(heightDiff) > 1) { return false; } else { return IsBalanced(root.left) && IsBalanced(root.right); } } private int GetHeight(TreeNode root) { // Base case if (root == null) { return 0; } // Recursive case return 1 + Math.Max(GetHeight(root.left), GetHeight(root.right)); } }