Grokking Tree Coding Patterns for Interviews

0% completed

​

Solution: Zigzag Traversal

Problem Statement

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.

Example 1:

Example 2:

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000

Solution

This problem follows the Binary Tree Level Order Traversal pattern. We can follow the same BFS approach

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Athanasios Petsas

· 4 years ago

Or we could have a deque for currentLevel instead of a vector and alternate from push_back to push_front.

Show 3 replies
R

Richard Yuan

· 4 years ago

For the python solution, at the end of each level we run "result.append(list(currentLevel))" to convert the deque into a list. Wouldn't this effectively make the time complexity O(n^2) in the worst case since we have to copy the elements of the deque into a list?

Similar to the DFS problem "All Paths for a Sum" where the time complexity came out to O(n^2) or O(nlogn) unless I am missing something.

Show 1 reply
V

venkatlearning11

· 3 years ago

Requirement is move right to left but did not happen for 1,7

Current output :

Zigzag traversal: [[12], [1, 7], [9, 10, 5], [17, 20]]

Instead of

Zigzag traversal: [[12], [7,1], [9, 10, 5], [17, 20]]

A

Adeel Qureshi

· 3 years ago

Traceback (most recent call last): File "/box/Parsers.py", line 69, in parse return json.loads(line) File "/usr/lib/python3.7/json/init.py", line 348, in loads return _default_decoder.decode(s) File "/usr/lib/python3.7/json/decoder.py", line 337, in decode obj, end = self.raw_decode(s, idx=_w(s, 0).end()) File "/usr/lib/python3.7/json/decoder.py", line 355, in raw_decode raise JSONDecodeError("Expecting value", s, err.value) from None json.decoder.JSONDecodeError: Expecting value: line 1 column 2 (char 1)

Show 2 replies
Bruno Ely

Bruno Ely

· 2 years ago

In the Reverse Level Order Traversal problem, we still printed each level left-to-right. It only changed the top-to-bottom order to bottom-to-top.

E

eesahk

· a year ago

Can we just do the regular BFS level by level and then reverse at the end of each level?

frontier = deque()
frontier.append(root)
visited = set()
level = 0
while frontier:
    next_frontier = deque()
    curr_level = []
    for curr_node in frontier:
        visited.add(curr_node)
        curr_level.append(curr_node.val)
        if curr_node.left and curr_node.left not in visited:
            next_frontier.append(curr_node.left)
        if curr_node.right and curr_node.right not in visited:
            next_frontier.append(curr_node.right)
      
    if not level % 2 == 0:
		    curr_level = curr_level[::-1]
    result.append(curr_level)
    frontier = next_frontier
    level += 1