Balanced Binary Tree Leetcode Problem 110 [Python Solution]
In this blog post, we will dive into the LeetCode problem titled Balanced Binary Tree This is an easy-level problem that falls under the category of trees and is often encountered in technical interviews, especially at companies like Amazon.
We will provide a detailed Python solution, along with explanations, for this problem.
Problem Overview
The problem statement goes as follows: Given a binary tree, determine if it is height-balanced.
A binary tree is considered height-balanced if, for every node in the tree, the heights of its left and right subtrees differ by at most one.
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].
- The values of the nodes in the tree are within the range of -104 to 104. Now, let's break down the problem and understand how to approach it.
Understanding the Constraints
The constraints in this problem are relatively straightforward.
We are given a binary tree, and we need to determine whether it's height-balanced or not.
To solve this problem efficiently, we'll use a depth-first search (DFS) approach.
We'll explore the tree while keeping track of the heights of the left and right subtrees, ensuring they differ by at most one.
Balanced Binary Tree LeetCode Problem Solution
Bruteforce Approach
Before we dive into the efficient approach, let's briefly discuss a naive or bruteforce approach.
The naive approach would involve starting from the root and checking the balance for each node.
This would result in revisiting the same nodes multiple times, making it inefficient.
Efficient Approach with Python Code Solution
Now, let's explore the efficient approach and the Python code solution for the Balanced Binary Tree problem.
To efficiently solve this problem, we'll use a recursive DFS approach that calculates the height of subtrees while simultaneously checking for balance.
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: Optional[TreeNode]) -> bool:
def dfs(root):
if not root:
return [True, 0]
left, right = dfs(root.left), dfs(root.right)
balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
return [balanced, 1 + max(left[1], right[1])]
return dfs(root)[0]
In this solution, we define a TreeNode class to represent nodes in the binary tree.
The isBalanced method checks if the tree is balanced or not.
The dfs function is a helper function that performs a depth-first search on the tree while calculating the height of subtrees and checking for balance.
The function dfs returns a list with two values:
1. A boolean indicating whether the subtree is balanced (True or False).
2. The height of the subtree.
The recursive DFS starts from the root and goes down to the leaf nodes.
It checks the balance for each subtree while calculating their heights.
If, at any point, it detects an imbalance, it sets the balance flag to False.
The height of each subtree is calculated as the maximum height between the left and right subtrees, plus one for the current node.
The final result is determined by the balance flag.
If it's True for the entire tree, the function returns True, indicating that the binary tree is height-balanced.
Otherwise, it returns False.
Time and Space Complexity
Before we conclude, let's analyze the time and space complexity of our solution.
Time Complexity:
The time complexity of our solution is O(n), where n is the number of nodes in the binary tree.
We visit each node once, performing a constant amount of work at each node.
Space Complexity:
The space complexity is O(h), where h is the height of the binary tree.
In the worst case, where the tree is completely unbalanced (essentially a linked list), the space complexity becomes O(n).
However, in a balanced binary tree, the space complexity is O(log n), which is the height of the tree.
Reasoning Behind Our Approach
We chose this approach because it efficiently addresses the problem's requirements while avoiding redundant work.
By recursively calculating the height of subtrees and checking for balance during the same traversal, we eliminate the need to revisit nodes, resulting in an optimal solution with a time complexity of O(n).
In summary, the Balanced Binary Tree problem is solved by ensuring that the heights of the left and right subtrees for each node differ by at most one.
We use a recursive DFS approach to efficiently calculate the height of subtrees and check for balance, resulting in an optimal solution.
Related Interview Questions By Company:
Related Interview Questions By Difficulty:
- Kth Smallest Element In A BST LeetCode
- Insert Into A Binary Search Tree LeetCode
- Binary Tree Preorder Traversal LeetCode
Related Interview Questions By Category:
Conclusion
In this blog post, we discussed the LeetCode problem Balanced Binary Tree We provided a detailed Python solution, explained the efficient approach using recursive depth-first search, and analyzed the time and space complexity.
This problem is a great example of how to optimize a solution by eliminating redundant work, resulting in an optimal solution with a time complexity of O(n).
If you found this post helpful, please like and engage to support our our platform.
If you have any questions or suggestions, feel free to comment below.
Happy coding!
Question Link: Balanced Binary Tree on LeetCode
