Binary Tree Zigzag Level Order Traversal

Data Structures and Algorithms

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).

Links

data_structures_algorithms/algorithms/bfs/binary_tree_zigzag_level_order_traversal at main ·…