Boundary of Binary Tree
Understanding the Problem
The boundary is the outline of the tree traced anti-clockwise: start at the root, go down the left side, sweep across the bottom (the leaves), and come back up the right side.
The boundary has three distinct parts:
- Left boundary: Start from the root's left child and keep going down, preferring the left child at each step. If there's no left child, take the right child instead. Stop before you reach a leaf.
- Leaves: All leaf nodes collected from left to right across the entire tree.
- Right boundary: Start from the root's right child and keep going down, preferring the right child at each step. If there's no right child, take the left child instead. Stop before you reach a leaf. This list gets reversed because we're tracing anti-clockwise (bottom-up).
The root is always included first (unless the tree is empty). The main complication is double-counting: a leaf at the end of the left or right boundary path must not appear twice, so the boundary definitions explicitly exclude the leftmost leaf from the left boundary and the rightmost leaf from the right boundary. Those two nodes belong to the leaves section only.
Key Constraints:
1 <= number of nodes <= 10^4→ A linear traversal handles this size comfortably, and every reasonable solution here is O(n).-1000 <= Node.val <= 1000→ Node values can be negative and can repeat. We collect values, not node references, so equal values at different positions both appear in the output.
Approach 1: Three Separate Traversals
Intuition
Break the problem into the three parts the statement describes, collect each separately, and concatenate them.
The left boundary is a single walk down from root.left: at each node take the left child if it exists, otherwise the right child, and stop before reaching a leaf. The right boundary is the mirror image starting from root.right, except its values are needed bottom-up, so collect them top-down into a temporary list and reverse it.
For the leaves, a DFS that recurses into the left subtree before the right one encounters childless nodes in left-to-right order, so appending each leaf as it is found produces the middle section directly.
Excluding leaves from both boundary walks is what prevents double-counting: the leftmost and rightmost leaves are picked up once, by the leaf pass, even though the boundary walks end right above them.
Algorithm
- If the root is null, return an empty list.
- Add the root's value to the result.
- If the root is a leaf (no children), return the result containing only the root.
- Collect the left boundary: start from
root.left, walk down preferring left children, stop before any leaf. Add each node's value to the result. - Collect all leaves: do a DFS traversal of the entire tree. Add every leaf's value to the result.
- Collect the right boundary: start from
root.right, walk down preferring right children, stop before any leaf. Store values in a temporary list, then reverse it and append to the result. - Return the result.
Visualization and Code
Loading animation...
- Time Complexity: O(n). The leaf collection visits every node once via DFS and dominates. The two boundary walks each visit at most h nodes, where h is the tree height.
- Space Complexity: O(n). The result list holds up to n values. The leaf-collection recursion stack and the temporary right-boundary list each add O(h), which is O(n) worst case for a skewed tree.
This approach makes three separate passes over different parts of the tree. The next approach visits each node once and classifies it on the spot, using a flag passed down from its parent.
Approach 2: Single Preorder Traversal with Flags
Intuition
A single preorder traversal can classify every node if each recursive call knows which role the node plays: left boundary, right boundary, or neither. The parent passes this role down as a flag. Whether a node is on a boundary is fully determined by its parent's flag and its position, so no second pass is needed.
The flag propagation mirrors the problem's definition. A left boundary node's left child inherits the LEFT flag; its right child inherits it only when there is no left child, because the boundary follows the leftmost available path. The right boundary is symmetric. Every other child gets the NONE flag.
Preorder visits left boundary nodes before any leaf and visits leaves in left-to-right order, so two of the three sections come out already ordered. The right boundary is the one piece preorder produces top-down when the output needs it bottom-up, so it goes into a separate list that is reversed during the final assembly.
Classification checks for a leaf before checking the flag. A leaf goes to the leaves list even when it carries a boundary flag, so the node at the bottom of each boundary path (the leftmost or rightmost leaf) is recorded once, among the leaves. This single ordering rule replaces the "stop before a leaf" logic from Approach 1.
Algorithm
- If the root is null, return an empty list.
- Initialize three lists:
leftBoundary,leaves,rightBoundary. - Run a preorder DFS starting from the root. For each node, pass a flag indicating if it's a left boundary node, a right boundary node, or neither.
- At each node, check for a leaf first: a leaf goes to
leavesregardless of its flag. Otherwise a LEFT-flagged node goes toleftBoundaryand a RIGHT-flagged node goes torightBoundary. - Propagate flags to children: a LEFT flag goes to the left child, or to the right child when there is no left child. The RIGHT flag is symmetric. All other children get NONE.
- Combine: [root.val] + leftBoundary + leaves + reverse(rightBoundary).
Example Walkthrough
Code
- Time Complexity: O(n). The preorder DFS visits each node once and does O(1) work per node: check for a leaf, classify, and append to a list. The final concatenation and reversal take O(n) total.
- Space Complexity: O(n). The result stores up to n values and the three auxiliary lists together hold at most n values. The recursion stack adds O(h), where h is the tree height (O(n) worst case for a skewed tree).