Binary Tree Zigzag Level Order Traversal

Sources: leetcode 103

Rating: medium

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def zigzagLevelOrder(root: TreeNode) -> List[List[int]]:
    # return the tree in zig zag level order

Solution

Iterate through the trees using a queue, starting with the root node and its level. Use a dictionary d to store information on each level with the level number being the keys and the list of node values being the value.

def zigzagLevelOrder(root):
    if root is None:
        return []
    queue = [(root, 0)]
    d = {}
    while queue:
        node, level = queue.pop(0)
        # iterate through tree
    return [d[i] for i in range(len(d))]

If it is the first node of the level to be seen, create the new key. Otherwise, add the node value to the growing list of values. Then add the child nodes to the queue

def zigzagLevelOrder(root):
    if root is None:
        return []
    queue = [(root, 0)]
    d = {}
    while queue:
        node, level = queue.pop(0)
        if level in d:
            d[level].append(node.val)
        else:
            d[level] = [node.val]
        if node.left: queue.append((node.left, level+1))
        if node.right: queue.append((node.right, level+1))
    # rearrange to zig zag order
    return [d[i] for i in range(len(d))]

Finally, go through the stored level order and reverse every other list to obtain zig zag order.

Final Code

def zigzagLevelOrder(root):
    if root is None:
        return []
    queue = [(root, 0)]
    d = {}
    while queue:
        node, level = queue.pop(0)
        if level in d:
            d[level].append(node.val)
        else:
            d[level] = [node.val]
        if node.left: queue.append((node.left, level+1))
        if node.right: queue.append((node.right, level+1))
    for k, v in d.items():
        if k % 2 == 1:
            v.reverse()
    return [d[i] for i in range(len(d))]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s