Teaching Kids Programming: Videos on Data Structures and Algorithms
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.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: trueExample 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output: falseExample 3:
Input: root = []
Output: true
Top Down Recursive Algorithm to Determine a Balanced Binary Tree
We know the Recursive Algorithm to Compute the depth for a given binary tree in O(N) time:
1 2 3 4 5 6 | def depth(root): if not root: return 0 left = depth(root.left) right = depth(root.right) return max(left, right) + 1 |
def depth(root):
if not root:
return 0
left = depth(root.left)
right = depth(root.right)
return max(left, right) + 1A Binary Tree is balanced as long as its left tree and right tree are also balanced (for every node, in recursive definition), also the depth of the left sub tree and right sub tree is no more than 1 (also needs to be satisfied in recursive manner).
1 2 3 4 5 6 7 8 9 10 11 12 | # 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: TreeNode) -> bool: if root is None: return True return self.isBalanced(root.left) and self.isBalanced(root.right) and \ abs(depth(root.left) - depth(root.right)) <= 1 |
# 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: TreeNode) -> bool:
if root is None:
return True
return self.isBalanced(root.left) and self.isBalanced(root.right) and \
abs(depth(root.left) - depth(root.right)) <= 1However, the time complexity is O(NLogN) not optimial.
Bottom Up Algorithm to Check Balanced Binary Tree
Based on the Recursive Depth Function, we know the heights of a node’s left and right subtree, then we can invalidate the result once we find the difference is more than 1.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | # 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: TreeNode) -> bool: self.ans = True def depth(root): if not root: return 0 left = depth(root.left) right = depth(root.right) if abs(left - right) > 1: self.ans = False return max(left, right) + 1 depth(root) return self.ans |
# 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: TreeNode) -> bool:
self.ans = True
def depth(root):
if not root:
return 0
left = depth(root.left)
right = depth(root.right)
if abs(left - right) > 1:
self.ans = False
return max(left, right) + 1
depth(root)
return self.ansThe time complexity is the same as getting the height of a binary tree. We can also return a tuple where the first value indicates if the current tree is balanced, and the second value is the height of the tree. The time complexity is O(N).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # 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: TreeNode) -> bool: if root is None: return True def depth(root): if not root: return True, 0 leftBalanced, left = depth(root.left) if not leftBalanced: return False, 0 rightBalanced, right = depth(root.right) if not rightBalanced: return False, 0 return abs(left - right) <= 1, max(left, right) + 1 return depth(root)[0] |
# 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: TreeNode) -> bool:
if root is None:
return True
def depth(root):
if not root:
return True, 0
leftBalanced, left = depth(root.left)
if not leftBalanced:
return False, 0
rightBalanced, right = depth(root.right)
if not rightBalanced:
return False, 0
return abs(left - right) <= 1, max(left, right) + 1
return depth(root)[0]–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Index with Equal Left and Right Sums (Prefix and Suffix Sum Algorithm)
Next Post: Teaching Kids Programming - Estimate the Math Continued Fraction Value in Python (Recursion and Iterative Algorithm)