Binary Tree Vertical Order Traversal

🎯

Binary Tree Vertical Order Traversal

mediumTREEFacebookAmazonBloomberg

Imagine you are looking at a binary tree from the side and want to see all nodes aligned vertically, grouped by their horizontal distance from the root.

💡 This problem requires understanding how to traverse a tree while tracking horizontal positions (columns). Beginners often struggle because it combines BFS traversal with coordinate tracking and sorting, which is not a straightforward tree traversal.

📋

Problem Statement

Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column). If two nodes are in the same row and column, the order should be from left to right.

The number of nodes in the tree is in the range [1, 10^5].Node values are integers in the range [-10^9, 10^9].

💡

Example

Input"root = [3,9,20,null,null,15,7]"

Output[[9],[3,15],[20],[7]]

The vertical columns are: column -1: [9], column 0: [3,15], column 1: [20], column 2: [7]. Nodes are listed top to bottom, left to right.

• Single node tree → [[node_value]]
• All nodes aligned in a single vertical line → all nodes in one list
• Tree with multiple nodes in the same column and row → order by left to right
• Empty tree (null root) → []

⚠️

Common Mistakes

Not tracking column indices correctly

Nodes appear in wrong vertical groups or output is incorrect

✅ Ensure left child column = parent column - 1, right child column = parent column + 1

Using DFS without sorting nodes properly

Output order is incorrect when multiple nodes share same column and row

✅ Either sort nodes by row and value after DFS or use BFS to preserve order

Not handling empty tree input

Code crashes or returns null instead of empty list

✅ Add explicit check for null root and return empty list

Sorting nodes inefficiently multiple times

Unnecessary performance overhead, possibly TLE on large inputs

✅ Sort once after collecting all nodes or use BFS to avoid sorting all nodes

Using unordered map without tracking min and max columns

Output columns in arbitrary order, failing problem requirements

✅ Track min and max column indices or use ordered map to output columns in order

🧠

Brute Force (DFS with manual sorting)

💡 This approach exists to build intuition by collecting all nodes with their coordinates and then sorting them. It is straightforward but inefficient for large trees.

Intuition

Traverse the tree using DFS, record each node's (row, column) coordinates, then sort all nodes by column, then row, then value to get the vertical order.

Algorithm

1. Traverse the tree with DFS, tracking row and column indices for each node.
2. Store tuples of (column, row, node_value) in a list.
3. Sort the list by column, then row, then node value.
4. Group the sorted nodes by column to form the final output.

💡 The main challenge is understanding how to assign and use coordinates, and then how sorting simulates vertical order traversal.

</>

Code

from collections import defaultdict

def verticalOrder(root):
    nodes = []
    def dfs(node, row, col):
        if not node:
            return
        nodes.append((col, row, node.val))
        dfs(node.left, row + 1, col - 1)
        dfs(node.right, row + 1, col + 1)
    dfs(root, 0, 0)
    nodes.sort()
    res = defaultdict(list)
    for col, row, val in nodes:
        res[col].append(val)
    return [res[x] for x in sorted(res)]

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

root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(verticalOrder(root))

Line Notes

nodes = []Initialize list to store nodes with coordinates

def dfs(node, row, col):DFS helper to traverse tree with row and column tracking

if not node:Base case to stop recursion at leaf's child

nodes.append((col, row, node.val))Record node with its column and row for sorting

dfs(node.left, row + 1, col - 1)Left child is one row down and one column left

dfs(node.right, row + 1, col + 1)Right child is one row down and one column right

nodes.sort()Sort nodes by column, then row, then value to get vertical order

res = defaultdict(list)Group nodes by column after sorting

for col, row, val in nodes:Populate groups for each column

return [res[x] for x in sorted(res)]Return columns in ascending order

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    static class NodeInfo implements Comparable<NodeInfo> {
        int col, row, val;
        NodeInfo(int c, int r, int v) { col = c; row = r; val = v; }
        public int compareTo(NodeInfo other) {
            if (this.col != other.col) return this.col - other.col;
            if (this.row != other.row) return this.row - other.row;
            return this.val - other.val;
        }
    }

    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<NodeInfo> nodes = new ArrayList<>();
        dfs(root, 0, 0, nodes);
        Collections.sort(nodes);
        List<List<Integer>> res = new ArrayList<>();
        int prevCol = Integer.MIN_VALUE;
        for (NodeInfo ni : nodes) {
            if (ni.col != prevCol) {
                res.add(new ArrayList<>());
                prevCol = ni.col;
            }
            res.get(res.size() - 1).add(ni.val);
        }
        return res;
    }

    private void dfs(TreeNode node, int row, int col, List<NodeInfo> nodes) {
        if (node == null) return;
        nodes.add(new NodeInfo(col, row, node.val));
        dfs(node.left, row + 1, col - 1, nodes);
        dfs(node.right, row + 1, col + 1, nodes);
    }

    // Main method for testing
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        Solution sol = new Solution();
        System.out.println(sol.verticalOrder(root));
    }
}

Line Notes

class NodeInfo implements Comparable<NodeInfo>Helper class to store node info and enable sorting

public int compareTo(NodeInfo other)Defines sorting order by column, then row, then value

dfs(root, 0, 0, nodes);Start DFS traversal with initial coordinates

if (node == null) return;Base case to stop recursion

nodes.add(new NodeInfo(col, row, node.val));Record node with coordinates

dfs(node.left, row + 1, col - 1, nodes);Traverse left child with updated coordinates

dfs(node.right, row + 1, col + 1, nodes);Traverse right child with updated coordinates

Collections.sort(nodes);Sort all nodes to simulate vertical order

if (ni.col != prevCol)Detect column change to start new group

res.get(res.size() - 1).add(ni.val);Add node value to current column group

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

struct NodeInfo {
    int col, row, val;
    NodeInfo(int c, int r, int v) : col(c), row(r), val(v) {}
    bool operator<(const NodeInfo& other) const {
        if (col != other.col) return col < other.col;
        if (row != other.row) return row < other.row;
        return val < other.val;
    }
};

void dfs(TreeNode* node, int row, int col, vector<NodeInfo>& nodes) {
    if (!node) return;
    nodes.emplace_back(col, row, node->val);
    dfs(node->left, row + 1, col - 1, nodes);
    dfs(node->right, row + 1, col + 1, nodes);
}

vector<vector<int>> verticalOrder(TreeNode* root) {
    vector<NodeInfo> nodes;
    dfs(root, 0, 0, nodes);
    sort(nodes.begin(), nodes.end());
    vector<vector<int>> res;
    int prevCol = INT_MIN;
    for (auto& ni : nodes) {
        if (ni.col != prevCol) {
            res.emplace_back();
            prevCol = ni.col;
        }
        res.back().push_back(ni.val);
    }
    return res;
}

// Driver code
int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    auto res = verticalOrder(root);
    for (auto& col : res) {
        cout << "[";
        for (int v : col) cout << v << ",";
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

struct NodeInfoStores node coordinates and value for sorting

bool operator<(const NodeInfo& other) constDefines sorting order by col, row, then val

void dfs(TreeNode* node, int row, int col, vector<NodeInfo>& nodes)DFS traversal with coordinate tracking

if (!node) return;Base case to stop recursion

nodes.emplace_back(col, row, node->val);Record node info for sorting

dfs(node->left, row + 1, col - 1, nodes);Traverse left child with updated coordinates

dfs(node->right, row + 1, col + 1, nodes);Traverse right child with updated coordinates

sort(nodes.begin(), nodes.end());Sort nodes to simulate vertical order

if (ni.col != prevCol)Detect column change to start new group

res.back().push_back(ni.val);Add node value to current column group

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function verticalOrder(root) {
    const nodes = [];
    function dfs(node, row, col) {
        if (!node) return;
        nodes.push([col, row, node.val]);
        dfs(node.left, row + 1, col - 1);
        dfs(node.right, row + 1, col + 1);
    }
    dfs(root, 0, 0);
    nodes.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        if (a[1] !== b[1]) return a[1] - b[1];
        return a[2] - b[2];
    });
    const res = [];
    let prevCol = Number.MIN_SAFE_INTEGER;
    for (const [col, row, val] of nodes) {
        if (col !== prevCol) {
            res.push([]);
            prevCol = col;
        }
        res[res.length - 1].push(val);
    }
    return res;
}

// Driver code
const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(verticalOrder(root));

Line Notes

const nodes = []Initialize array to store nodes with coordinates

function dfs(node, row, col)DFS helper to traverse tree with coordinate tracking

if (!node) return;Base case to stop recursion

nodes.push([col, row, node.val]);Record node with column and row for sorting

dfs(node.left, row + 1, col - 1);Traverse left child with updated coordinates

dfs(node.right, row + 1, col + 1);Traverse right child with updated coordinates

nodes.sort((a, b) => {...})Sort nodes by column, then row, then value

if (col !== prevCol)Detect column change to start new group

res.push([]);Create new group for new column

res[res.length - 1].push(val);Add node value to current column group

⏱

Complexity

TimeO(n log n)

SpaceO(n)

DFS visits all nodes once (O(n)), sorting all nodes takes O(n log n), grouping is O(n).

💡 For n=1000 nodes, sorting 1000 elements is about 1000*log2(1000) ≈ 10,000 operations, which is acceptable but not optimal.

Interview Verdict: Accepted but not optimal for very large trees

This approach works but sorting all nodes is costly; better BFS approaches exist that avoid sorting all nodes.

🧠

BFS with Column Tracking and Hash Map

💡 This approach uses BFS to traverse level by level, tracking columns and grouping nodes on the fly, avoiding sorting all nodes at the end.

Intuition

Use a queue to perform BFS, track each node's column index, and store nodes in a hash map keyed by column. This preserves top-to-bottom and left-to-right order naturally.

Algorithm

1. Initialize a queue with the root node and its column index 0.
2. While the queue is not empty, pop nodes level by level.
3. For each node, add its value to the list corresponding to its column in a map.
4. Add left and right children to the queue with column indices col-1 and col+1 respectively.
5. After BFS, extract the columns from the map in sorted order to form the result.

💡 BFS ensures nodes are processed top to bottom and left to right naturally, so no sorting by row is needed.

</>

Code

from collections import deque, defaultdict

def verticalOrder(root):
    if not root:
        return []
    col_table = defaultdict(list)
    queue = deque([(root, 0)])
    min_col = max_col = 0
    while queue:
        node, col = queue.popleft()
        col_table[col].append(node.val)
        min_col = min(min_col, col)
        max_col = max(max_col, col)
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    return [col_table[x] for x in range(min_col, max_col + 1)]

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

root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(verticalOrder(root))

Line Notes

if not root:Handle empty tree edge case

col_table = defaultdict(list)Map columns to list of node values

queue = deque([(root, 0)])Initialize BFS queue with root at column 0

node, col = queue.popleft()Process nodes in FIFO order for BFS

col_table[col].append(node.val)Add node value to its column group

min_col = min(min_col, col)Track minimum column index seen

max_col = max(max_col, col)Track maximum column index seen

if node.left: queue.append((node.left, col - 1))Add left child with column one less

if node.right: queue.append((node.right, col + 1))Add right child with column one more

return [col_table[x] for x in range(min_col, max_col + 1)]Return columns in order from left to right

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Map<Integer, List<Integer>> colTable = new HashMap<>();
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 0));
        int minCol = 0, maxCol = 0;
        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> p = queue.poll();
            TreeNode node = p.getKey();
            int col = p.getValue();
            colTable.putIfAbsent(col, new ArrayList<>());
            colTable.get(col).add(node.val);
            minCol = Math.min(minCol, col);
            maxCol = Math.max(maxCol, col);
            if (node.left != null) queue.offer(new Pair<>(node.left, col - 1));
            if (node.right != null) queue.offer(new Pair<>(node.right, col + 1));
        }
        for (int i = minCol; i <= maxCol; i++) {
            res.add(colTable.get(i));
        }
        return res;
    }

    // Main method for testing
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        Solution sol = new Solution();
        System.out.println(sol.verticalOrder(root));
    }
}

// Helper Pair class if needed
class Pair<K, V> {
    private K key;
    private V value;
    public Pair(K key, V value) { this.key = key; this.value = value; }
    public K getKey() { return key; }
    public V getValue() { return value; }
}

Line Notes

if (root == null) return res;Handle empty tree edge case

Map<Integer, List<Integer>> colTable = new HashMap<>();Map columns to list of node values

Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();Queue for BFS storing node and column

queue.offer(new Pair<>(root, 0));Start BFS with root at column 0

Pair<TreeNode, Integer> p = queue.poll();Dequeue node and its column

colTable.putIfAbsent(col, new ArrayList<>());Initialize list for column if absent

colTable.get(col).add(node.val);Add node value to its column group

minCol = Math.min(minCol, col);Track minimum column index

maxCol = Math.max(maxCol, col);Track maximum column index

if (node.left != null) queue.offer(new Pair<>(node.left, col - 1));Add left child with column one less

if (node.right != null) queue.offer(new Pair<>(node.right, col + 1));Add right child with column one more

for (int i = minCol; i <= maxCol; i++) { res.add(colTable.get(i)); }Collect columns in order

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<vector<int>> verticalOrder(TreeNode* root) {
    if (!root) return {};
    map<int, vector<int>> colTable;
    queue<pair<TreeNode*, int>> q;
    q.push({root, 0});
    int minCol = 0, maxCol = 0;
    while (!q.empty()) {
        auto [node, col] = q.front(); q.pop();
        colTable[col].push_back(node->val);
        minCol = min(minCol, col);
        maxCol = max(maxCol, col);
        if (node->left) q.push({node->left, col - 1});
        if (node->right) q.push({node->right, col + 1});
    }
    vector<vector<int>> res;
    for (int c = minCol; c <= maxCol; ++c) {
        res.push_back(colTable[c]);
    }
    return res;
}

// Driver code
int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    auto res = verticalOrder(root);
    for (auto& col : res) {
        cout << "[";
        for (int v : col) cout << v << ",";
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

if (!root) return {};Handle empty tree edge case

map<int, vector<int>> colTable;Ordered map to store nodes by column

queue<pair<TreeNode*, int>> q;Queue for BFS storing node and column

q.push({root, 0});Start BFS with root at column 0

auto [node, col] = q.front(); q.pop();Dequeue node and its column

colTable[col].push_back(node->val);Add node value to its column group

minCol = min(minCol, col);Track minimum column index

maxCol = max(maxCol, col);Track maximum column index

if (node->left) q.push({node->left, col - 1});Add left child with column one less

if (node->right) q.push({node->right, col + 1});Add right child with column one more

for (int c = minCol; c <= maxCol; ++c) { res.push_back(colTable[c]); }Collect columns in order

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function verticalOrder(root) {
    if (!root) return [];
    const colTable = new Map();
    const queue = [[root, 0]];
    let minCol = 0, maxCol = 0;
    while (queue.length > 0) {
        const [node, col] = queue.shift();
        if (!colTable.has(col)) colTable.set(col, []);
        colTable.get(col).push(node.val);
        minCol = Math.min(minCol, col);
        maxCol = Math.max(maxCol, col);
        if (node.left) queue.push([node.left, col - 1]);
        if (node.right) queue.push([node.right, col + 1]);
    }
    const res = [];
    for (let c = minCol; c <= maxCol; c++) {
        res.push(colTable.get(c));
    }
    return res;
}

// Driver code
const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(verticalOrder(root));

Line Notes

if (!root) return [];Handle empty tree edge case

const colTable = new Map();Map columns to list of node values

const queue = [[root, 0]];Initialize BFS queue with root at column 0

const [node, col] = queue.shift();Dequeue node and its column

if (!colTable.has(col)) colTable.set(col, []);Initialize list for column if absent

colTable.get(col).push(node.val);Add node value to its column group

minCol = Math.min(minCol, col);Track minimum column index

maxCol = Math.max(maxCol, col);Track maximum column index

if (node.left) queue.push([node.left, col - 1]);Add left child with column one less

if (node.right) queue.push([node.right, col + 1]);Add right child with column one more

for (let c = minCol; c <= maxCol; c++) { res.push(colTable.get(c)); }Collect columns in order

⏱

Complexity

TimeO(n)

SpaceO(n)

BFS visits each node once (O(n)), and grouping by column is O(n). No sorting of all nodes is needed.

💡 For n=1000 nodes, this means roughly 1000 operations, which is efficient and scalable.

Interview Verdict: Accepted and optimal for large inputs

This approach is preferred in interviews because it is efficient and clean, leveraging BFS and hash maps.

🧠

BFS with Column Tracking and TreeMap / Ordered Map (Java/C++ variant)

💡 This approach is similar to approach 2 but uses an ordered map to keep columns sorted automatically, simplifying the final output step.

Intuition

Use BFS with a queue and an ordered map keyed by column to store nodes. The ordered map keeps columns sorted, so no separate sorting step is needed.

Algorithm

1. Initialize a queue with the root node and column 0.
2. Initialize an ordered map (TreeMap in Java, map in C++) to store column to node list.
3. Perform BFS, adding nodes to their column list in the map.
4. Add children with updated columns to the queue.
5. Return the values of the ordered map as the result.

💡 The ordered map removes the need to track min and max columns or sort keys later.

</>

Code

from collections import deque
from sortedcontainers import SortedDict

def verticalOrder(root):
    if not root:
        return []
    col_table = SortedDict()
    queue = deque([(root, 0)])
    while queue:
        node, col = queue.popleft()
        if col not in col_table:
            col_table[col] = []
        col_table[col].append(node.val)
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    return list(col_table.values())

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

root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(verticalOrder(root))

Line Notes

from sortedcontainers import SortedDictUse SortedDict to maintain keys in sorted order automatically

col_table = SortedDict()Initialize ordered map for columns

queue = deque([(root, 0)])Initialize BFS queue with root at column 0

node, col = queue.popleft()Dequeue node and its column

if col not in col_table: col_table[col] = []Initialize list for column if absent

col_table[col].append(node.val)Add node value to its column group

if node.left: queue.append((node.left, col - 1))Add left child with column one less

if node.right: queue.append((node.right, col + 1))Add right child with column one more

return list(col_table.values())Return columns in ascending order automatically

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        TreeMap<Integer, List<Integer>> colTable = new TreeMap<>();
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 0));
        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> p = queue.poll();
            TreeNode node = p.getKey();
            int col = p.getValue();
            colTable.putIfAbsent(col, new ArrayList<>());
            colTable.get(col).add(node.val);
            if (node.left != null) queue.offer(new Pair<>(node.left, col - 1));
            if (node.right != null) queue.offer(new Pair<>(node.right, col + 1));
        }
        for (List<Integer> list : colTable.values()) {
            res.add(list);
        }
        return res;
    }

    // Main method for testing
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        Solution sol = new Solution();
        System.out.println(sol.verticalOrder(root));
    }
}

// Helper Pair class if needed
class Pair<K, V> {
    private K key;
    private V value;
    public Pair(K key, V value) { this.key = key; this.value = value; }
    public K getKey() { return key; }
    public V getValue() { return value; }
}

Line Notes

TreeMap<Integer, List<Integer>> colTable = new TreeMap<>();Ordered map keeps columns sorted automatically

queue.offer(new Pair<>(root, 0));Start BFS with root at column 0

Pair<TreeNode, Integer> p = queue.poll();Dequeue node and column

colTable.putIfAbsent(col, new ArrayList<>());Initialize list for column if absent

colTable.get(col).add(node.val);Add node value to column group

if (node.left != null) queue.offer(new Pair<>(node.left, col - 1));Add left child with column one less

if (node.right != null) queue.offer(new Pair<>(node.right, col + 1));Add right child with column one more

for (List<Integer> list : colTable.values()) { res.add(list); }Collect columns in ascending order

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<vector<int>> verticalOrder(TreeNode* root) {
    if (!root) return {};
    map<int, vector<int>> colTable;
    queue<pair<TreeNode*, int>> q;
    q.push({root, 0});
    while (!q.empty()) {
        auto [node, col] = q.front(); q.pop();
        colTable[col].push_back(node->val);
        if (node->left) q.push({node->left, col - 1});
        if (node->right) q.push({node->right, col + 1});
    }
    vector<vector<int>> res;
    for (auto& [col, nodes] : colTable) {
        res.push_back(nodes);
    }
    return res;
}

// Driver code
int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    auto res = verticalOrder(root);
    for (auto& col : res) {
        cout << "[";
        for (int v : col) cout << v << ",";
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

map<int, vector<int>> colTable;Ordered map keeps columns sorted automatically

queue<pair<TreeNode*, int>> q;Queue for BFS storing node and column

q.push({root, 0});Start BFS with root at column 0

auto [node, col] = q.front(); q.pop();Dequeue node and column

colTable[col].push_back(node->val);Add node value to column group

if (node->left) q.push({node->left, col - 1});Add left child with column one less

if (node->right) q.push({node->right, col + 1});Add right child with column one more

for (auto& [col, nodes] : colTable) { res.push_back(nodes); }Collect columns in ascending order

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function verticalOrder(root) {
    if (!root) return [];
    const colTable = new Map();
    const queue = [[root, 0]];
    while (queue.length > 0) {
        const [node, col] = queue.shift();
        if (!colTable.has(col)) colTable.set(col, []);
        colTable.get(col).push(node.val);
        if (node.left) queue.push([node.left, col - 1]);
        if (node.right) queue.push([node.right, col + 1]);
    }
    const sortedKeys = Array.from(colTable.keys()).sort((a, b) => a - b);
    return sortedKeys.map(k => colTable.get(k));
}

// Driver code
const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(verticalOrder(root));

Line Notes

if (!root) return [];Handle empty tree edge case

const colTable = new Map();Map columns to list of node values

const queue = [[root, 0]];Initialize BFS queue with root at column 0

const [node, col] = queue.shift();Dequeue node and column

if (!colTable.has(col)) colTable.set(col, []);Initialize list for column if absent

colTable.get(col).push(node.val);Add node value to column group

if (node.left) queue.push([node.left, col - 1]);Add left child with column one less

if (node.right) queue.push([node.right, col + 1]);Add right child with column one more

const sortedKeys = Array.from(colTable.keys()).sort((a, b) => a - b);Sort keys to get columns in order

return sortedKeys.map(k => colTable.get(k));Return columns in ascending order

⏱

Complexity

TimeO(n log k)

SpaceO(n)

BFS is O(n), inserting into ordered map is O(log k) per node where k is number of columns, total O(n log k).

💡 For balanced trees, k is about O(n), so worst case is O(n log n), but usually k << n making this efficient.

Interview Verdict: Accepted and efficient, especially in languages with built-in ordered maps

This approach is a good alternative when ordered maps are available, simplifying code and ensuring sorted output.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 (BFS with hash map) is the best choice for most interviews due to simplicity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS + sort all nodes)	O(n log n)	O(n)	Yes (deep recursion)	Yes	Mention only - never code
2. BFS with Column Tracking and Hash Map	O(n)	O(n)	No	Yes	Code this approach
3. BFS with Column Tracking and Ordered Map	O(n log k)	O(n)	No	Yes	Good alternative if language supports ordered maps

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and ask about input format and output expectations.State the brute force approach: DFS with coordinate recording and sorting.Explain why sorting all nodes is costly and introduce BFS with column tracking.Discuss how BFS preserves top-to-bottom and left-to-right order naturally.Mention ordered map variant if language supports it for cleaner code.Write clean, tested code and walk through examples.Discuss time and space complexity and possible edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Understanding of BFS and DFS, coordinate tracking, data structures like hash maps and ordered maps, and ability to optimize from brute force to efficient BFS.

Common Follow-ups

• What if nodes in the same row and column need to be sorted by value? → Use DFS with sorting or priority queues.
• How to handle very large trees efficiently? → BFS with hash map is optimal.
• Can you do vertical order traversal without extra space? → No, column tracking requires extra space.
• How to extend to top or bottom view? → Modify BFS to keep only first or last node per column.

💡 These follow-ups test deeper understanding of ordering, optimization, and variations of vertical traversal.

🔍

Pattern Recognition

When to Use

1) Problem involves tree traversal, 2) Requires grouping nodes by vertical columns, 3) Ordering nodes top-to-bottom and left-to-right matters, 4) BFS or coordinate tracking is needed.

Signature Phrases

vertical order traversalcolumn by columntop to bottom, left to right

NOT This Pattern When

Problems that only require level order traversal without column grouping or problems focused on subtree sums.

Similar Problems

Binary Tree Right Side View - similar vertical perspective but only rightmost nodesVertical Order Traversal II - adds sorting by row and valueTop View of Binary Tree - only topmost nodes per column

Practice

1. Given the following code for the right side view of a binary tree, what is the final output when run on this tree? Tree structure: - Root = 1 - Root.left = 2 - Root.right = 3 - Root.left.right = 5 - Root.right.right = 4

from typing import Optional, List
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rightSideView(root: Optional[TreeNode]) -> List[int]:
    rightside = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(rightside):
            rightside.append(node.val)
        dfs(node.right, depth + 1)
        dfs(node.left, depth + 1)
    dfs(root, 0)
    return rightside

print(rightSideView(root))  # What is printed?

easy

A. [1, 3, 5]

B. [1, 2, 5]

C. [1, 3, 4]

D. [1, 2, 4]

Solution

1. Step 1: Trace dfs at depth 0

   Start at root (1), depth=0, rightside is empty, so append 1.

2. Step 2: Traverse right subtree first

   At depth=1, visit node 3, append 3 since rightside length=1. Then visit node 4 at depth=2, append 4.

3. Step 3: Traverse left subtree

   At depth=1, node 2 is visited but depth=1 already in rightside, so skip append. Node 5 at depth=2 is skipped since depth=2 already in rightside.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Output matches expected right side view [OK]

Hint: Right-first DFS appends first node per depth [OK]

Common Mistakes:

• Appending left nodes at same depth overwrites right nodes
• Confusing order of traversal causing wrong nodes appended
• Off-by-one errors in depth indexing

2. You are given a binary tree and need to find the shortest distance from the root node down to the nearest leaf node. Which algorithmic approach guarantees the optimal solution with minimal time complexity?

easy

A. Breadth-First Search (BFS) stopping at the first encountered leaf node

B. Dynamic Programming storing minimum depths for subtrees and combining results

C. Depth-First Search (DFS) exploring all paths to leaves and returning the minimum depth

D. Greedy approach choosing the child with the smaller value at each step

Solution

1. Step 1: Understand the problem requirement

   The problem asks for the minimum depth to a leaf node, which means the shortest path from root to any leaf.

2. Step 2: Identify the algorithm that finds shortest path in unweighted trees

   BFS explores nodes level by level and stops immediately when it finds the first leaf, ensuring the shortest path is found efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS stops at first leaf -> minimal depth found [OK]

Hint: Shortest path in trees -> BFS with early stop [OK]

Common Mistakes:

• Assuming DFS always finds minimum depth efficiently
• Confusing greedy value-based choice with shortest path
• Thinking DP is needed for simple tree traversal

3. The following code attempts to connect next right pointers in any binary tree. Identify the line containing the subtle bug that causes incorrect next pointer connections for nodes with only one child.

def connect(root):
    if not root:
        return null

    if root.left and root.right:
        root.left.next = root.right

    next_node = root.next
    while next_node:
        if next_node.left:
            next_child = next_node.left
            break
        if next_node.right:
            next_child = next_node.right
            break
        next_node = next_node.next
    else:
        next_child = null

    if root.right:
        root.right.next = next_child
    if root.left:
        root.left.next = next_child

    connect(root.right)
    connect(root.left)

    return root

medium

A. Line: if root.left: root.left.next = next_child

B. Line: if root.right: root.right.next = next_child

C. Line: if root.left and root.right: root.left.next = root.right

D. Line: connect(root.right)

Solution

1. Step 1: Analyze next pointer assignments

   When both children exist, left.next -> right is set correctly. For single child cases, next_child is found from root.next chain.

2. Step 2: Identify bug in single child handling

   Both if root.right and if root.left set their next to next_child unconditionally. This causes left child to overwrite its next pointer even if right child exists, breaking correct connections.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing if root.left to elif root.left fixes the bug [OK]

Hint: Use elif to avoid overwriting next pointers for left child [OK]

Common Mistakes:

• Setting both left and right child's next unconditionally
• Not breaking after setting left.next when right child exists
• Misordering recursive calls

4. Suppose the problem is modified so that the binary tree nodes can be reused multiple times (i.e., the tree can have cycles or repeated references). Which modification to the BFS with indexing approach is necessary to correctly compute the maximum width?

hard

A. Add a visited set to avoid infinite loops and repeated counting of nodes.

B. No modification needed; BFS with indexing works as is.

C. Switch to DFS with memoization to handle repeated nodes.

D. Use a priority queue to process nodes in order of their indices.

Solution

1. Step 1: Understand the impact of node reuse

   Reusing nodes or cycles cause infinite loops in BFS if nodes are revisited repeatedly.

2. Step 2: Modify BFS to track visited nodes

   Adding a visited set prevents revisiting the same node multiple times, avoiding infinite loops and incorrect width calculation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Visited set is essential to handle cycles or repeated nodes [OK]

Hint: Use visited set to prevent infinite loops in graphs [OK]

Common Mistakes:

• Assuming tree nodes cannot be reused
• Not adding visited set causing infinite loops
• Switching to DFS unnecessarily

5. Suppose you want to modify the level order traversal to return the nodes in reverse level order (from bottom level to top). Which of the following approaches correctly achieves this without increasing time complexity beyond O(n)?

hard

A. Perform BFS but insert each level's list at the front of the result list during traversal

B. Perform normal BFS and then reverse the final list of levels before returning

C. Modify BFS to enqueue children at the front of the queue instead of the back

D. Use DFS to collect nodes by level and then reverse the collected list

Solution

1. Step 1: Understand reversing levels efficiently

   Performing normal BFS and then reversing the final list of levels is straightforward and maintains O(n) time complexity.

2. Step 2: Analyze insertion at front complexity

   Inserting each level at the front of a list during BFS can be O(n) per insertion if using a Python list, leading to O(n²) total time.

3. Step 3: Evaluate other options

   Using DFS and then reversing uses extra stack space; modifying BFS queue order breaks BFS semantics.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Reversing the final list after BFS is simple, correct, and efficient [OK]

Hint: Perform BFS normally and reverse result list to get reverse level order efficiently [OK]

Common Mistakes:

• Inserting at front of list during BFS can cause O(n²) time