We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Vertical Order Traversal of a Binary Tree

Difficulty: Hard

Problem Description

Given the root of a binary tree, calculate the vertical order traversal of the binary tree. The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Key Insights

  • Each node can be represented by its coordinates (row, col), where the root starts at (0, 0).
  • Left children decrease the column index (col - 1) and increase the row index (row + 1).
  • Right children increase the column index (col + 1) and also increase the row index (row + 1).
  • Use a map to store nodes in each column, where each column stores a list of nodes sorted by their row index and value for nodes in the same position.

Space and Time Complexity

Time Complexity: O(N log N), where N is the number of nodes (due to sorting of nodes in the same column). Space Complexity: O(N), for storing the nodes in the column map.

Solution

We can perform a Breadth-First Search (BFS) or Depth-First Search (DFS) to traverse the tree and collect nodes based on their vertical columns. A hashmap (or dictionary) can be used to map each column index to a list of tuples containing the row index and the node value. Finally, we sort the entries in each column by row index and value, and return the result.

Code Solutions

from collections import defaultdict
import heapq

def verticalTraversal(root):
    col_table = defaultdict(list)
    def DFS(node, row, col):
        if node:
            # Append the node's value with its row and column index
            col_table[col].append((row, node.val))
            # Traverse left and right children
            DFS(node.left, row + 1, col - 1)
            DFS(node.right, row + 1, col + 1)

    DFS(root, 0, 0)
    
    # Sort the column indices
    sorted_columns = sorted(col_table.keys())
    result = []
    
    for col in sorted_columns:
        # Sort by row first, then by value
        column_nodes = sorted(col_table[col])
        # Extract the node values only
        result.append([val for row, val in column_nodes])
    
    return result
← Back to All Questions