Binary Tree Zigzag Level Order Traversal
Statement
Given a binary tree, return its zigzag level order traversal. The zigzag level order traversal corresponds to traversing nodes from left to right for one level, and then right to left for the next level, and so on, reversing direction after every level.
Constraints
- 0 ≤ number of nodes ≤ 500
- -100 ≤
node.data
≤ 100
Solution
"""
production algorithm
"""
from collections import deque
class Solution:
def zigzag_level_order(self, root):
"""
time complexity O(n)
space complexity O(n)
"""
if root is None:
return list()
current, next, result = deque(), deque(), list()
next.append(root)
# next level exists
while next:
current, next = next, deque()
result.append(list())
# next element of level exists
while current:
# pop from left to right
if len(result) % 2 == 1:
node = current.popleft()
result[-1].append(node.data)
if node.left:
next.append(node.left)
if node.right:
next.append(node.right)
# pop from right to left
else:
node = current.pop()
result[-1].append(node.data)
if node.right:
next.appendleft(node.right)
if node.left:
next.appendleft(node.left)
return result
"""
unit tests
"""
from unittest import TestCase
from algorithms.bfs.binary_tree_zigzag_level_order_traversal.solution import Solution
from data_structures.binary_tree.binary_tree import BinaryTreeNode
class SolutionTestCase(TestCase):
def test_zigzag_level_order(self):
# Given
root = BinaryTreeNode(-6)
root.left = BinaryTreeNode(-15)
root.right = BinaryTreeNode(7)
root.left.left = BinaryTreeNode(-18)
root.left.right = BinaryTreeNode(-11)
root.right.left = BinaryTreeNode(1)
root.right.right = BinaryTreeNode(17)
root.left.left.left = BinaryTreeNode(-19)
root.left.left.right = BinaryTreeNode(-17)
root.left.right.left = BinaryTreeNode(-12)
root.left.right.right = BinaryTreeNode(-8)
root.right.left.left = BinaryTreeNode(-5)
root.right.left.right = BinaryTreeNode(6)
root.right.right.left = BinaryTreeNode(13)
root.right.right.right = BinaryTreeNode(20)
solution = Solution()
# When
actual = solution.zigzag_level_order(root)
# Then
expected = [[-6], [7, -15], [-18, -11, 1, 17],
[20, 13, 6, -5, -8, -12, -17, -19]]
self.assertEqual(actual, expected)
Strategy
Breadth First Search.
Explanation
The algorithm uses two queues. One queue is used to hold the elements of the current level of the binary tree. The second queue is used to hold the elements of the next level of the binary tree, i.e. the children of the current level.
When the current level has odd parity, then the nodes are read from left to right. Also, when the current level has even parity, then the nodes are read from right to left. When a node is read, its children are added to the next queue.
Time Complexity
Every node of the binary tree is visited once. Therefore, the time complexity of the algorithm is O(n)
.
Space Complexity
In the case of a perfect binary tree, at each level the number of nodes in the binary tree doubles. In other words, the last level of the binary tree has half the nodes of the binary tree. So, the number of nodes in the last level of the binary tree is proportional to n
, where n
is the number of nodes in the binary tree.
Now, the algorithm builds a queue with the nodes of the next level of the binary tree. Eventually, the algorithm builds the queue with the nodes of the last level of the binary tree. Since the number of nodes in the last level of the binary tree is proportional to n
, then the auxiliary space of the queue is proportional to n
. Therefore, the auxiliary space complexity of the algorithm is O(n)
.