DSA problem
Boundary of Binary Tree
The boundary of a binary tree is the concatenation of its left boundary, the leaves (left to right), and the reversed right boundary. The left boundary is the path from the root following the leftmost edges down to (but not including) any leaf; the right boundary is similarly the rightmost path. If a node is both the root and a leaf — a tree of size one — the answer is simply that node.
The challenge is partitioning the work cleanly into three sub-traversals so each node is reported at most once and in the right order. Three pieces:
- Left boundary (top-down, excluding leaves): Walk from
root.left, always preferringnode.left; ifnode.leftis null fall through tonode.right. Skip leaves. - Leaves (depth-first, left-to-right): A standard preorder traversal that emits a node only when it has no children.
- Right boundary (bottom-up, excluding leaves): Same as the left boundary but mirrored — prefer
node.rightelsenode.left— collected then reversed so it reads from bottom up to the root.
The concatenation is root → left boundary → leaves → reversed right boundary. Subtle points: do not include leaves twice (the left/right boundary walks must skip leaves), and handle the degenerate case where the tree is just a root. The algorithm visits each node a constant number of times across the three traversals, so the total work is O(n) with O(h) recursion space.
Examples
root = [1,null,2,3,4][1,3,4,2]root = [1,2,3,4,5,6,null,null,null,7,8,9,10][1,2,4,7,8,9,10,6,3]root = [1][1]Constraints
- The number of nodes in the tree is in the range [1, 10^4].
- -1000 <= Node.val <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.