⚖️110. Balanced Binary Tree
Easy | Grind 75 | September 5th Moday, 2022
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.
Constraints:
The number of nodes in the tree is in the range
[0, 5000].-10^4 <= Node.val <= 10^4
Input: root = [3,9,20,null,null,15,7]
Output: true
SOLUTION
Although easy, I did struggle with this question a little bit. The point I missed was that the tree needs to be balanced at every node and not just the root. This is why example 4 is an unbalanced tree.
To check if a binary tree is balanced, we need to compare the height of the left and right subtrees at each node. If the height difference is greater than 1, then the tree is not balanced. To do that, we will build a bottom-up approach.
We recursively traverse the tree until the leaf node. The leaf nodes are guaranteed to be balanced since both the left and right subtrees are null. Therefore, we return True (indicating it is balanced) and 0 (indicating height). These values are returned by both the left and the right subtree which are then compared to see if the subtrees are firstly balanced and the height difference between the two subtrees. The current leaf node then returns whether it is balanced (a boolean value) and a height. Height is calculated by adding 1 (the current node) to the maximum height returned by the subtrees. This is repeated from the bottom up until we reach the original root node. While We check if the right and the left subtree are balanced for every node.
# Definition for a binary tree node.
# 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:
result = self.find_balance(root)
return result[0]
def find_balance(self, root):
"""
bottom up approach to get height and check balance of a tree
param:
root: tree node
return:
balanced: is the seen tree balanced
height: max height the tree
"""
if not root:
return [True, 0]
left = self.find_balance(root.left)
right = self.find_balance(root.right)
# tree is balanced if the left and right has height difference f 1 or less
balanced = left[0] and right[0] and abs(left[1]-right[1]) < 2
# return the maximum height: either left or right and add 1 account for current node
height = max(left[1], right[1])+1
return balanced, height
TIME AND SPACE COMPLEXITY
TIME: O(n) where n is the number of nodes in the tree. Given that we traverse to each node and check the subtrees, the runtime is O(n)
SPACE: O(1) we only use two variables: balanced and height which store a boolean and an integer respectively. We could do away with the two variables but defining them makes the code more readable.
Last updated