Skills for tackling LeetCode problems - Tree Breadth First Search.
BFS can efficiently solve problems involving the traversal of a tree in a level-by-level order. It is usually implemented with a Queue to keep track of all the nodes of a level before jumping into the next level. Therefore, the space complexity is O(W) where W is the max number of nodes on any level. The time complexity is O(H) where H is the max height of the tree.
1. Binary Tree Level order Traversal
Given a binary tree, populate an array to represent its level-by-level traversal. You should populate the values of all nodes of each level from left to right in separate sub arrays.
# Time complexity O(N), where N is the total number of nodes in the tree.
# Space complexity O(N), as we need a queue to store values of all nodes.
from collections import deque
# class TreeNode:
# def __init__(self, val):
# self.val = val
# self.left, self.right = None, None
def traverse(root):
result = []
if root is None: return result
queue = deque()
queue.append(root)
while queue:
levelSize = len(queue) # number of nodes on each level
currentLevel = [] # store values of nodes on each level
for _ in range(levelSize): # for nodes on each level
currentNode = queue.popleft()
currentLevel.append(currentNode.val) # append that node
if currentNode.left: # push left child of that node into queue
queue.append(currentNode.left)
if currentNode.right: # push right child of that node into queue
queue.append(currentNode.right)
result.append(currentLevel)
return result
2. Reverse Level Order Traversal
Given a binary tree, populate an array to represent its level-by-level traversal in reverse order, i.e., the lowest level comes first. You should populate the values of all nodes in each level from left to right in separate sub-arrays.
# Time complexity O(N). Space complexity O(N).
def traverse(root):
result = deque() # allow appendleft
if root is None: return result
queue = deque()
queue.append(root)
while queue:
levelSize = len(queue)
currentLevel = []
for _ in range(levelSize):
currentNode = queue.popleft()
currentLevel.append(currentNode.val)
if currentNode.left:
queue.append(currentNode.left)
if currentNode.right:
queue.append(currentNode.right)
result.appendleft(currentLevel) # append to the left
return list(result)
3. Zigzag Traversal
Given a binary tree, populate an array to represent its zigzag level order traversal. You should populate the values of all nodes of the first level from left to right, then right to left for the next level and keep alternating in the same manner for the following levels.
# Time complexity O(N). Space complexity O(N).
def traverse(root):
result = []
if root is None: return result
queue = deque()
queue.append(root)
flag = True
while queue:
levelSize = len(queue)
currentLevel = deque() # allow appendleft
for _ in range(levelSize):
currentNode = queue.popleft()
# determine the order of nodes in a level
if flag:
currentLevel.append(currentNode.val)
else:
currentLevel.appendleft(currentNode.val)
if currentNode.left:
queue.append(currentNode.left)
if currentNode.right:
queue.append(currentNode.right)
result.append(list(currentLevel))
flag = not flag
return result
4. Level Averages in a Binary Tree
Given a binary tree, populate an array to represent the averages of all of its levels.
# Time complexity O(N). Space complexity O(N).
def find_level_averages(root):
result = []
if root is None:
return result
queue = deque()
queue.append(root)
while queue: # iterate through each level
levelSize = len(queue)
levelSum = 0.0 # store the sum of values in a level
for _ in range(len(queue)): # iterate through nodes in a level
currentNode = queue.popleft()
levelSum += currentNode.val # add up all values
if currentNode.left:
queue.append(currentNode.left)
if currentNode.right:
queue.append(currentNode.right)
result.append(levelSum / levelSize) # calcualte the average
return result
Similar problem: find the largest value on each level of a binary tree.
def find_level_max(root):
result = []
if root is None:
return result
queue = deque()
queue.append(root)
while queue: # iterate through each level
levelSize = len(queue)
levelMax = 0 # store the sum of values in a level
for _ in range(len(queue)): # iterate through nodes in a level
currentNode = queue.popleft()
levelMax = max(levelMax, currentNode.val) # find the max value
if currentNode.left:
queue.append(currentNode.left)
if currentNode.right:
queue.append(currentNode.right)
result.append(levelMax)
return result
5. Minimum Depth of a Binary Tree
Find the minimum depth of a binary tree. The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.
# Time complexity O(N). Space complexity O(N).
def find_minimum_depth(root):
if root is None:
return 0
queue = deque()
queue.append(root)
MIN = 0
while queue:
MIN += 1
for _ in range(len(queue)):
currentNode = queue.popleft()
# check if this is a leaf node
if not currentNode.left and not currentNode.right:
return MIN
# append the childs to the queue
if currentNode.left:
queue.append(currentNode.left)
if currentNode.right:
queue.append(currentNode.right)
Similar problem: Find the maximum depth.
# Time complexity O(N). Space complexity O(N).
def find_maximum_depth(root):
if root is None: return 0
queue = deque()
queue.append(root)
MAX = 0
while queue:
MAX += 1
for _ in range(len(queue)):
currentNode = queue.popleft()
if currentNode.left:
queue.append(currentNode.left)
if currentNode.right:
queue.append(currentNode.right)
return MAX
6. Level Order Successor
Given a binary tree and a node, find the level order successor of the given node in the tree. The level order successor is the node that appears right after the given node in the level order traversal.
# Time complexity O(N). Space complexity O(N).
def find_successor(root, key):
if root is None:
return None
queue = deque()
queue.append(root)
while queue:
currentNode = queue.popleft()
if currentNode.left:
queue.append(currentNode.left)
if currentNode.right:
queue.append(currentNode.right)
if currentNode.val == key: # found, return the first element in queue
break
return queue[0] if queue else None
7. Connect Level Order Siblings
Given a binary tree, connect each node with its level order successor. The last node of each level should point to a null node.
# Time complexity O(N). Space complexity O(N).
def connect_level_order_siblings(root):
if root is None:
return
queue = deque()
queue.append(root)
while queue:
pre = None # initiate a pointer
for _ in range(len(queue)):
currentNode = queue.popleft()
# connect nodes
if pre:
pre.next = currentNode
pre = currentNode
if currentNode.left:
queue.append(currentNode.left)
if currentNode.right:
queue.append(currentNode.right)
