Skip to content

Boundary and Views

Coordinates Make Trees Spatial

So far, every tree problem treated nodes as abstract values in a hierarchy. This lesson changes that. You're going to assign coordinates to every node — column, row, or both — and use those coordinates to answer spatial questions.

The problems in this lesson all share one trait: the algorithm is straightforward, but the edge cases are where you'll get burned in an interview. Pay close attention to the boundary conditions.

Tree with column coordinates assigned: root at column 0, left children at column-1, right children at column+1

Problem 1: Boundary Traversal

Problem: Return the boundary of a binary tree as a single list, going: root → left boundary (top-down) → leaves (left-to-right) → right boundary (bottom-up).

            1
          /   \
         2     3
        / \   / \
       4   5 6   7
          / \
         8   9

Expected boundary: [1, 2, 4, 8, 9, 6, 7, 3]

This breaks into three parts:

  1. Left boundary: walk down the left edge, excluding leaves. Path: 1, 2.
  2. Leaves: all leaf nodes left-to-right. Path: 4, 8, 9, 6, 7.
  3. Right boundary: walk down the right edge, excluding leaves, then reverse. Path: 3.

The root is included once (in the left boundary). Leaves are included once (in the leaves pass). The tricky part: what counts as "left boundary" vs "leaf"?

The left boundary is the path you'd walk if you always went left, falling back to right only when left doesn't exist. It stops before hitting a leaf.

Edge Cases That Break Naive Solutions

Case 1: Root with only one child. If root has no right child, the right boundary is empty — don't reverse-walk down the left side again.

Case 2: Left boundary node has only a right child. Node 2 has both children, so you go left to 4. But if node 2 had no left child and only a right child, you'd follow the right child — it's still part of the left boundary because it's the leftmost reachable non-leaf.

Case 3: Overlap between boundary and leaves. Node 4 is a leaf AND the end of the left boundary walk. Don't include it twice — the left boundary collection stops before leaves.

The Code

bool isLeaf(TreeNode* node) {
    return node && !node->left && !node->right;
}

void collectLeftBoundary(TreeNode* node, vector<int>& boundary) {
    if (!node || isLeaf(node)) return;
    boundary.push_back(node->val);
    if (node->left) collectLeftBoundary(node->left, boundary);
    else collectLeftBoundary(node->right, boundary);
}

void collectLeaves(TreeNode* node, vector<int>& boundary) {
    if (!node) return;
    if (isLeaf(node)) {
        boundary.push_back(node->val);
        return;
    }
    collectLeaves(node->left, boundary);
    collectLeaves(node->right, boundary);
}

void collectRightBoundary(TreeNode* node, vector<int>& boundary) {
    if (!node || isLeaf(node)) return;
    if (node->right) collectRightBoundary(node->right, boundary);
    else collectRightBoundary(node->left, boundary);
    boundary.push_back(node->val);
}

vector<int> boundaryTraversal(TreeNode* root) {
    if (!root) return {};
    vector<int> boundary;
    boundary.push_back(root->val);
    collectLeftBoundary(root->left, boundary);
    collectLeaves(root->left, boundary);
    collectLeaves(root->right, boundary);
    collectRightBoundary(root->right, boundary);
    return boundary;
}

Notice collectRightBoundary adds the value after the recursive call — that's how you get bottom-up order without an explicit reverse.

Also notice we call collectLeftBoundary(root->left, ...) and collectRightBoundary(root->right, ...) — starting from root's children, not root itself. The root is added separately to avoid duplication.

Complexity: \(O(n)\) time, \(O(h)\) space.

Problem 2: Top View and Bottom View

Problem: The top view of a tree is what you'd see looking down from above. For each vertical column, report the first node encountered (topmost). The bottom view reports the last node (bottommost).

Assign every node a column coordinate: root is column 0, going left is column \(-1\), going right is column \(+1\).

        1 (col 0)
       / \
      2   3 (col -1, col +1)
       \  /
        4 5 (col 0, col 0)

Top view: columns \(-1, 0, 1\) → nodes \(2, 1, 3\). Bottom view: columns \(-1, 0, 1\) → nodes \(2, 5, 3\). (Node 5 is deeper than 4 in column 0, but BFS processes level-by-level so 5 appears after 4 — last one wins.)

Full Trace: Top View with BFS

We use BFS so nodes are processed level-by-level. For top view, first node seen at each column wins.

Step Node Column Column Map Action
1 1 0 {0: 1} col 0 first seen → record
2 2 -1 {-1: 2, 0: 1} col -1 first seen → record
3 3 1 {-1: 2, 0: 1, 1: 3} col 1 first seen → record
4 4 0 {-1: 2, 0: 1, 1: 3} col 0 already seen → skip
5 5 0 {-1: 2, 0: 1, 1: 3} col 0 already seen → skip

Top view (sorted by column): [2, 1, 3].

For bottom view, change the logic: every node overwrites its column entry. Last one wins.

The Code

vector<int> topView(TreeNode* root) {
    if (!root) return {};
    map<int, int> columnToValue;
    queue<pair<TreeNode*, int>> bfsQueue;
    bfsQueue.push({root, 0});

    while (!bfsQueue.empty()) {
        auto [node, column] = bfsQueue.front();
        bfsQueue.pop();
        if (columnToValue.find(column) == columnToValue.end()) {
            columnToValue[column] = node->val;
        }
        if (node->left) bfsQueue.push({node->left, column - 1});
        if (node->right) bfsQueue.push({node->right, column + 1});
    }

    vector<int> result;
    for (auto& [col, val] : columnToValue) {
        result.push_back(val);
    }
    return result;
}

vector<int> bottomView(TreeNode* root) {
    if (!root) return {};
    map<int, int> columnToValue;
    queue<pair<TreeNode*, int>> bfsQueue;
    bfsQueue.push({root, 0});

    while (!bfsQueue.empty()) {
        auto [node, column] = bfsQueue.front();
        bfsQueue.pop();
        columnToValue[column] = node->val;
        if (node->left) bfsQueue.push({node->left, column - 1});
        if (node->right) bfsQueue.push({node->right, column + 1});
    }

    vector<int> result;
    for (auto& [col, val] : columnToValue) {
        result.push_back(val);
    }
    return result;
}

The only difference between top view and bottom view: top view uses find to skip already-seen columns, bottom view always overwrites. Same BFS, same column tracking.

Problem 3: Vertical Order Traversal (LC 987)

Problem: Return all nodes grouped by column, sorted by row within each column, and by value if row and column are equal.

This is the general version. Each node gets coordinates \((column, row)\): root is \((0, 0)\), left child is \((column - 1, row + 1)\), right child is \((column + 1, row + 1)\).

Full Trace

        1 (0,0)
       / \
      2   3 (−1,1) (+1,1)
     / \   \
    4   5   7 (−2,2) (0,2) (+2,2)
Node Column Row
1 0 0
2 -1 1
3 1 1
4 -2 2
5 0 2
7 2 2

Group by column, sort by row within each group:

  • Column \(-2\): [4]
  • Column \(-1\): [2]
  • Column \(0\): [1, 5] (row 0 before row 2)
  • Column \(1\): [3]
  • Column \(2\): [7]

Result: [[4], [2], [1, 5], [3], [7]]

The Code

vector<vector<int>> verticalTraversal(TreeNode* root) {
    if (!root) return {};
    map<int, vector<pair<int, int>>> columnMap;
    queue<tuple<TreeNode*, int, int>> bfsQueue;
    bfsQueue.push({root, 0, 0});

    while (!bfsQueue.empty()) {
        auto [node, column, row] = bfsQueue.front();
        bfsQueue.pop();
        columnMap[column].push_back({row, node->val});
        if (node->left) bfsQueue.push({node->left, column - 1, row + 1});
        if (node->right) bfsQueue.push({node->right, column + 1, row + 1});
    }

    vector<vector<int>> result;
    for (auto& [col, entries] : columnMap) {
        sort(entries.begin(), entries.end());
        vector<int> columnValues;
        for (auto& [row, val] : entries) {
            columnValues.push_back(val);
        }
        result.push_back(columnValues);
    }
    return result;
}

Complexity: \(O(n \log n)\) time (sorting within columns), \(O(n)\) space.

The Unifying Idea

All three problems — boundary, views, vertical order — require you to pass spatial information downward. The node itself doesn't know its column or row. You, the caller, tell it.

This is top-down thinking applied to coordinate systems. The tree's structure defines the coordinates, but the coordinates must be computed as you descend.

Try It

The starter code has a topView function with a TODO. Fill in the body using BFS with column tracking.

Input: [1, 2, 3, null, 4, 5, null]
Output: [2, 1, 3]

Predict before running: In a skewed tree (every node is a right child), what does the top view look like? Every node is in a different column, so the top view is the entire tree.

Challenge: What changes if two nodes share the same column and row in vertical order traversal, but you need to sort them by value? Look at how pair<int,int> sorting works — it sorts by first element, then second. The code already handles this correctly because we store {row, val}.

Edge Cases to Watch For

  • Boundary traversal: root overlaps all three parts. The root is simultaneously the left boundary, potentially a leaf, and the right boundary. It must appear exactly ONCE. Handle this by adding the root separately and starting left/right boundary collection from root->left and root->right to prevent triple-counting.
  • Vertical order tie-breaking: LC 987 requires that nodes at the same (column, row) be sorted by value. If you don't explicitly sort by value as a tiebreaker, two nodes at the same position will appear in arbitrary BFS order, which fails the test cases.

Problems

Problem Link Difficulty
LC 199 — Binary Tree Right Side View leetcode.com/problems/binary-tree-right-side-view Medium
LC 987 — Vertical Order Traversal leetcode.com/problems/vertical-order-traversal-of-a-binary-tree Hard
LC 545 — Boundary of Binary Tree leetcode.com/problems/boundary-of-binary-tree Medium