Katkat
Back

Vertical Order Traversal of a Binary Tree

AppleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to map tree nodes to a 2D coordinate system and group them based on their horizontal distance from the root, followed by specific sorting criteria.

Vertical Order Traversal

Given the root of a binary tree, return the vertical order traversal of its nodes' values.

Logic

  • The root is at column 0.
  • If a node is at column x, its left child is at x - 1 and its right child is at x + 1.
  • If two or more nodes share the same column, they should be ordered by their depth (top to bottom).
  • If nodes share the same column and the same depth, they must be ordered by their values in ascending order.

Function Signature

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def verticalTraversal(root: TreeNode) -> list[list[int]]:

Examples

Example 1: Input: root = [3, 9, 20, null, null, 15, 7] Output: [[9], [3, 15], [20], [7]] Explanation:

  • Column -1: [9]
  • Column 0: [3, 15]
  • Column 1: [20]
  • Column 2: [7]

Example 2: Input: root = [1, 2, 3, 4, 5, 6, 7] Output: [[4], [2], [1, 5, 6], [3], [7]] Explanation: Nodes 5 and 6 share the same column (0) and row (2). Since 5 < 6, 5 comes first.

Constraints

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

Hints

Hint 1

Use a hash map to group nodes by their column index, storing the values alongside their depth.

Hint 2

Perform a traversal (BFS or DFS) to record the `(column, row, value)` triplet for every node.

Hint 3

After collecting all triplets, sort them primarily by column, secondarily by row, and tertiarily by value.

Follow-up questions

  • How would your approach change if you needed to perform this traversal in a memory-constrained environment?
  • Could you implement this using an iterative approach rather than recursion, and what are the benefits?
  • What is the time and space complexity of your solution in terms of the number of nodes `N`?