Tree views — left, right, top, bottom, diagonal, boundary
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: []
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;}