Binary Tree Zigzag Level Order Traversal

  1. Both solutions are below.
    3
/ \
9 20
/ \
15 7
[
[3],
[20,9],
[15,7]
]
  1. If using a queue, or BFS approach, Notice that since its zigzag traversal, every other level is traversed left to right, and vice versa. We can use a mechanism ( e.g. level % 2 == 0) , to chose a. how to pop nodes from the queue, b. how and where to add children ( front or back) in order to follow the zigzag pattern
  1. A lot of visualization in the head is needed
# 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 zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:

if not root:
return None

res = []

q = collections.deque()
q.append(root)
level = 0

while q:
nodes_level = []

for _ in range(len(q)):
if level % 2 == 0:
# first root is traversed from left to right
# [node, node siblings from left to right ...]
node = q.popleft()
else:
# # [node siblings from left to right..., node]
node = q.pop()

nodes_level.append(node.val)

if level % 2 == 0:
# root's children will be traversed right to left, so
# we append left to the end of queue first and then append right.
# Children will be inserted [parents' siblings..., left, right]
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
else:
# Children will be inserted [left, right, ...parents' siblings]
if node.right:
q.insert(0, node.right)
if node.left:
q.insert(0, node.left)

level += 1
res.append(nodes_level)

return res
  • We visit each node once and only once.
  • In addition, the insertion operation on either end of the deque takes a constant time, rather than using the array/list data structure where the inserting at the head could take the O(K) time where KKis the length of the list.
  • Space Complexity: O(N) where NN is the number of nodes in the tree.
  • The main memory consumption of the algorithm is the node_queue that we use for the loop, apart from the array that we use to keep the final output.
  • As one can see, at any given moment, the node_queue would hold the nodes that are at most across two levels. Therefore, at most, the size of the queue would be no more than 2⋅L, assuming LL is the maximum number of nodes that might reside on the same level. Since we have a binary tree, the level that contains the most nodes could occur to consist all the leave nodes in a full binary tree, which is roughly L=N/2​. As a result, we have the space complexity of 2 * N/2=N in the worst case.
  1. We appendleft() for all the odd number levels ( 1,3,5 etc.).
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return
res = []

def traverse(node, level):
if len(res) == level:
res.append(collections.deque())

if level % 2 == 0:
res[level].append(node.val)
else:
res[level].appendleft(node.val)

if node.left: traverse(node.left, level+1)
if node.right: traverse(node.right, level+1)

traverse(root, 0)
return res
  • Same as the previous BFS approach, we visit each node once and only once.
  • Space Complexity: O(H), where H is the height of the tree, i.e. the number of levels in the tree, which would be roughly log⁡2N.
  • Unlike the BFS approach, in the DFS approach, we do not need to maintain the node_queue data structure for the traversal.
  • However, the function recursion would incur additional memory consumption on the function call stack. As we can see, the size of the call stack for any invocation of DFS(node, level) would be exactly the number of level that the current node resides on. Therefore, the space complexity of our DFS algorithm isO(log2​N) which is much better than the BFS approach.
  1. Jump Game IV
  2. Find Nearest Right Node in Binary Tree

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store