Vertical Order Traversal of Binary Tree

Data Structures and Algorithms

Statement

Given the root of a binary tree, find the vertical order traversal of a binary tree. In other words, find the values of the nodes from top to bottom in each column, column by column from left to right. If there’s more than one node in the same column and row, return the values from left to right.

Constraints

• 1 ≤ number of nodes ≤ 500
• 0 ≤ node.data ≤ 1000

Solution

"""
production algorithm
"""

from collections import defaultdict
from data_structures.queue.queue import Queue


class Solution:
    def vertical_order(self, root):
        """
        time complexity O(n)
        space complexity O(n)
        """
        indexer, queue = defaultdict(list), Queue()
        low, high = 0, 0
        queue.push((root, 0))
        while not queue.empty():
            node, column = queue.pop()
            low, high = min(low, column), max(high, column)
            indexer[column].append(node.data)
            if node.left:
                queue.push((node.left, column - 1))
            if node.right:
                queue.push((node.right, column + 1))
        result = [indexer[column] for column in range(low, high + 1)]
        return result

"""
unit tests
"""

from unittest import TestCase
from algorithms.bfs.vertical_order_traversal_of_binary_tree.solution import Solution
from data_structures.binary_tree.binary_tree import BinaryTreeNode


class SolutionTestCase(TestCase):
    def test_vertical_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.vertical_order(root)

        # Then
        expected = [[-19], [-18], [-15, -17, -12, -5],
                    [-6, -11, 1], [7, -8, 6, 13], [17], [20]]
        self.assertEqual(actual, expected)

Strategy

Breadth First Search.

Explanation

The algorithm uses a dictionary to hold the nodes of each column, and a queue for breadth first search. The algorithm also uses low and high pointers to know the lower and upper bounds of the number of columns. When a node is pushed to the queue, it’s pushed with its column too. Then, when a node is popped from the queue, it’s added to the list of nodes of that column in the dictionary. After traversal, then the vertical order traversal is returned.

Time Complexity

The algorithm visits every node of the binary tree. Therefore, the time complexity of the algorithm is O(n).

Space Complexity

At the end of traversal, the dictionary holds every node of the binary tree. Therefore, the auxiliary space complexity of the algorithm is O(n).

Links

data_structures_algorithms/algorithms/bfs/vertical_order_traversal_of_binary_tree at main ·…