Tree views — left, right, top, bottom, diagonal, boundary

Medium

Problem

Return what is visible from different sides of the tree:

Left / right view — the first / last node on each level. Top / bottom view — the first / last node seen in each vertical column (horizontal distance: root 0, left −1, right +1). Diagonal traversal — group nodes along lines of slope −1. Boundary traversal — the left boundary, then the leaves, then the right boundary in reverse, going anticlockwise.

Example 1

Input:  root = [1, 2, 3, 4, 5, 6, 7]
Output: left [1,2,4] · right [1,3,7] · top [4,2,1,3,7] · bottom [4,2,6,3,7] (5 and 6 share a column; the later one wins)

Also asked as: Left View of a tree · Right View of Tree · Top View of a tree · Bottom View of a tree · Diagnol Traversal of a Binary tree · Boundary traversal of a Binary tree

Test cases

Case 1

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

Case 2

Input:    [1,null,3]
Expected: [1,3]

Case 3

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution3 approaches

1. Left / Right view — first node seen per BFS level

Time O(n)Space O(width)

Level-order BFS; the first node dequeued at each level is the left view, the last is the right view.

function rightView(root) {
if (!root) return [];
const res = [], q = [root];
while (q.length) {
const n = q.length;
for (let i = 0; i < n; i++) {
const node = q.shift();
if (i === n - 1) res.push(node.val); // last of the level = right view
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
}
return res;
}

2. Top / Bottom view — by horizontal distance

Time O(n log n)Space O(n)

BFS carrying a horizontal distance (hd): left child hd−1, right child hd+1. Top view keeps the first node per hd; bottom view keeps the last. Sort by hd.

function bottomView(root) {
if (!root) return [];
const map = new Map();
const q = [[root, 0]];
while (q.length) {
const [node, hd] = q.shift();
map.set(hd, node.val); // last write wins ⇒ bottom
if (node.left) q.push([node.left, hd - 1]);
if (node.right) q.push([node.right, hd + 1]);
}
return [...map.entries()].sort((a, b) => a[0] - b[0]).map(([, v]) => v);
}
// Top view: same, but only set map if the hd is not already present.

3. Diagonal & boundary traversals

Time O(n)Space O(n)

Diagonal: right edges stay on the same diagonal, left edges start the next — use a queue of "diagonal starts". Boundary: left boundary (top-down, no leaves) + all leaves (left-to-right) + right boundary (bottom-up, no leaves).

function diagonal(root) {
const res = [];
let queue = root ? [root] : [];
while (queue.length) {
const next = [];
for (let node of queue) {
while (node) {
res.push(node.val);
if (node.left) next.push(node.left);
node = node.right;
}
}
queue = next;
}
return res;
}