411. Boundary of Binary Tree
You get the root of a binary tree (each node a TreeNode with fields val, left, right). Produce the values on the tree's boundary, walking it counter-clockwise: the root first, then the left boundary top-down, then every leaf from left to right, then the right boundary bottom-up. No node may appear twice.
The three pieces are defined precisely:
- Left boundary: start at
root.left; at each node step to the left child if it exists, otherwise to the right child; stop before reaching a leaf. Leaves are excluded, and the piece is empty whenroot.leftis null. - Leaves: every node with no children, in left-to-right order. The root never counts as a leaf, even when it has no children.
- Right boundary: the mirror image — start at
root.right, prefer the right child, else the left child, exclude leaves — and emit it bottom-up.
Return the boundary as a list of node values in that order.
Example 1:
Input: root = [1, 2, 3, 4, 5, 6, null, null, null, 7, 8, 9, 10]
Output: [1, 2, 4, 7, 8, 9, 10, 6, 3]
Explanation: Root 1. Left boundary: just 2 (its left child 4 is a leaf, so the walk stops before it). Leaves left-to-right: 4, 7, 8, 9, 10. Right boundary bottom-up: 6, then 3.
Example 2:
Input: root = [1, null, 2, 3, 4]
Output: [1, 3, 4, 2]
Explanation: There is no left subtree, so the left boundary is empty. The leaves are 3 and 4, and the right boundary (bottom-up, leaves excluded) is just 2.
Constraints:
- 1 ≤ number of nodes ≤ 10⁴
- -1000 ≤ Node.val ≤ 1000
Hints:
Break the answer into three independent pieces — a downward left-edge walk, a leaf collection, and a downward right-edge walk emitted in reverse — and glue them after the root.
The edge walks are iterative: from root.left keep taking left ?? right; from root.right keep taking right ?? left. Stop when you land on a leaf so leaves are only produced by the leaf pass.
Watch the overlaps: a tree whose root has a single child, or a leaf that terminates the left-boundary walk, must still appear exactly once.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 3, 4, 5, 6, null, null, null, 7, 8, 9, 10]
Expected output: [1, 2, 4, 7, 8, 9, 10, 6, 3]