Leetcode 110 - Balanced Binary Tree
Explanation for Leetcode 110 - Balanced Binary Tree problem, and its solution in Python.
Problem
Leetcode 110 - Balanced Binary Tree
Example:
.jpg)
1
2
Input: root = [3,9,20,null,null,15,7]
Output: true
.jpg)
1
2
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Approach
This problem can be solved by checking whether the left and right subtrees of each node are balanced by keeping track of the height of the tree. We can use a 2 length array to store if the tree is balanced and the height of the tree.
In base case, if the node is null, the tree is balanced since having no children means it is balanced, and we can put the height as 0.
For recursive case, we call the function recursively for the left and right subtrees, and store the result in a variable. The only way the tree is balanced is if both left and right subtrees are balanced, and the difference between the height of left and right subtree is not greater than 1.
Thus, we can return the result of the recursive function.
Visualization of the problem:
1
2
3
4
5
6
7
8
9
10
11
12
13
3
/ \
9 20
/ \
15 7
15: [True, 0] Since it has no children, it is balanced and the height is 0.
7: [True, 0] Since it has no children, it is balanced and the height is 0.
20: [True, 1] Since the left and right subtrees are balanced and the difference between the height of left and right subtree is 1, it is balanced and the height is 1.
9: [True, 0] Since it has no children, it is balanced and the height is 0.
3: [True, 1] Since the left and right subtrees are balanced and the difference between the height of left and right subtree is 1, it is balanced and the height is 1.
Thus, the tree is balanced, return True.
Here is the implementation of the approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
# Define a helper function to check if the tree is balanced
def dfs(root):
# If the node is null, the tree is balanced and the height is 0
if not root:
return [True, 0]
# Recursively call the function on the left and right subtrees
left, right = dfs(root.left), dfs(root.right)
# The tree is balanced if both left and right subtrees are balanced and the difference between the height of left and right subtree is not greater than 1
balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
# Return the result of the recursive function
return [balanced, 1 + max(left[1], right[1])]
return dfs(root)[0]
Time Complexity and Space Complexity
The time complexity of this approach is $O(n)$ since we are visiting each node once.
The space complexity is $O(n)$ since we are using a recursive function.