grid47 Exploring patterns and algorithms
Oct 27, 2024
5 min read
Solution to LeetCode 110: Balanced Binary Tree Problem
Given a binary tree, determine if it is height-balanced. A binary tree is considered height-balanced if for every node, the height of the left and right subtrees differs by no more than one.
Problem
Approach
Steps
Complexity
Input: The input is the root of a binary tree.
Example: root = [10, 5, 15, null, null, 12, 20]
Constraints:
• The number of nodes in the tree is in the range [0, 5000].
• -10^4 <= Node.val <= 10^4
Output: The output is a boolean value indicating whether the tree is height-balanced or not.
Example: true
Constraints:
• The tree is height-balanced if the height difference between the left and right subtrees of every node is no more than 1.
Goal: The goal is to check if the binary tree is balanced by verifying that the difference in heights of the left and right subtrees is at most 1 at each node.
Steps:
• For each node in the tree, calculate the height of its left and right subtrees recursively.
• If at any point the height difference is greater than 1, return false.
• Otherwise, return true if all nodes satisfy the balanced condition.
Goal: The solution must handle trees with a large number of nodes efficiently.
Steps:
• Ensure the solution works for trees with up to 5000 nodes.
Assumptions:
• The tree is a valid binary tree.
• Input: Input: root = [5,3,8,2,4,7,9]
• Explanation: The tree is balanced because the height difference between the left and right subtrees at each node is no more than 1.
• Input: Input: root = [1,2,2,3,3,null,null,4,4]
• Explanation: The tree is not balanced because the height difference between the left and right subtrees of node 2 is greater than 1.
Approach: To check if a binary tree is height-balanced, we need to traverse the tree and calculate the height of each subtree. If at any point the difference in height exceeds 1, we know the tree is not balanced.
Observations:
• We can perform a depth-first search (DFS) traversal of the tree while calculating the height of each subtree.
• A recursive approach is ideal because we can calculate the height of a subtree and check if it is balanced in a single pass.
Steps:
• Implement a helper function that calculates the height of a node's subtree and checks if it is balanced.
• For each node, calculate the heights of its left and right subtrees.
• If the height difference is greater than 1, return false.
• Return true if all subtrees are balanced.
Empty Inputs:
• If the input tree is empty, it is considered balanced.
Large Inputs:
• The solution should handle trees with up to 5000 nodes efficiently.
Special Values:
• The solution should handle trees where all nodes are on one side (unbalanced) and trees with balanced structures.
Constraints:
• The algorithm should run efficiently within the constraints of up to 5000 nodes.
boolisBalanced(TreeNode* root) {
if(!root) returntrue;
int l = h(root->left);
int r = h(root->right);
return abs(l - r) <=1&& isBalanced(root->left) && isBalanced(root->right);
}
inth(TreeNode* node) {
if(node ==NULL) return0;
int l = h(node->left);
int r = h(node->right);
return1+ max(l, r);
}
1 : Function Declaration
boolisBalanced(TreeNode* root) {
Define the main function to determine if a tree is balanced.
2 : Base Case
if(!root) returntrue;
Base case: If the tree is empty, it is balanced by definition.
3 : Recursive Call
int l = h(root->left);
Calculate the height of the left subtree by calling the helper function.
4 : Recursive Call
int r = h(root->right);
Calculate the height of the right subtree by calling the helper function.
5 : Condition Evaluation
return abs(l - r) <=1&&
Check if the difference in heights of left and right subtrees is at most 1.
6 : Recursive Call
isBalanced(root->left) &&
Recursively check if the left subtree is balanced.
7 : Recursive Call
isBalanced(root->right);
Recursively check if the right subtree is balanced.
8 : Function Declaration
inth(TreeNode* node) {
Define a helper function to compute the height of a tree.
9 : Base Case
if(node ==NULL) return0;
Base case: The height of an empty tree is 0.
10 : Recursive Call
int l = h(node->left);
Recursively calculate the height of the left subtree.
11 : Recursive Call
int r = h(node->right);
Recursively calculate the height of the right subtree.
12 : Height Calculation
return1+ max(l, r);
Return the height of the current node as 1 plus the maximum height of its subtrees.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: In the worst case, we traverse all nodes of the tree once, making the time complexity O(n).
Best Case: O(h)
Worst Case: O(h)
Description: The space complexity is O(h), where h is the height of the tree, due to the recursion stack.
