⚡Flashcard Drill➔
NeetCode #399LC-314MediumTreesNC Algo100
← Back to All Problems

#399 · #314 · Binary Tree Vertical Order Traversal(二叉树的垂序遍历)

📌 Problem Statement & Constraints

Given the root of a binary tree, return its vertical order traversal: a list of columns from leftmost to rightmost, where each column lists the node values top to bottom. Within a column, nodes at the same depth are ordered left to right. Constraints: the number of nodes is in [0, 1000].

💡 Core Algorithmic Approaches

  1. Assign each node a column index: the root is 0, the left child is column - 1, the right child column + 1.
  2. BFS is essential here, because it guarantees that nodes are appended in top-to-bottom order, and left-to-right within the same depth.
  3. Collect the values into a map from column to list, then emit the columns in ascending order.
  4. A DFS would need an extra sort key of (depth, order) to reproduce the same ordering.

💻 Benchmark Python3 Implementation

class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        from collections import defaultdict, deque
        if not root:
            return []
        cols = defaultdict(list)
        q = deque([(root, 0)])             # (node, column)
        while q:
            node, c = q.popleft()
            cols[c].append(node.val)
            if node.left:
                q.append((node.left, c - 1))
            if node.right:
                q.append((node.right, c + 1))
        return [cols[c] for c in sorted(cols)]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + w log w) where w is the number of distinct columns: the BFS is linear and the final sort is over the columns.
💾 Space Complexity
O(n) for the map and the queue.

⚠️ Interview Pitfalls & Follow-ups

  • Using DFS: it does not guarantee top-to-bottom ordering within a column; you would need to sort by depth and then by traversal order.
  • Forgetting to sort the columns: the map's key order is insertion order, not left-to-right.
  • Using a list indexed by column with an offset: it works, but the range of columns is unknown up front, making a dict safer.
  • Appending children in the wrong order: left must be pushed before right so the left-to-right tie-break holds.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems