Skip to main content

Tree Boundary Perimeter Walk

hard
TreeBinary TreeDepth First SearchDfs Recursive
Asked atAmazonGoogleMicrosoftUber

Problem Description

Given the root of a binary tree, return all values of nodes on the **boundary** of the tree in counter-clockwise order, starting from the root.

The boundary consists of three parts, in order:
1. **Left boundary**: nodes from root to the leftmost leaf (excluding the leaf itself).
2. **Leaf nodes**: all leaf nodes from left to right.
3. **Right boundary**: nodes from the rightmost leaf up to the root (excluding the root and the leaf itself), listed in **reverse** (bottom-up) order.

Note: If the root has no left or right subtree, the root itself counts as a leaf.

**Example 1:**
```
Input: root = [1, 2, 3, 4, 5, 6, 7, null, null, 8, 9]
Output: [1, 2, 4, 8, 9, 5, 6, 7, 3]
Explanation:
- Left boundary (excl. leaf): [1, 2]
- Leaves (left to right): [4, 8, 9, 5, 6, 7]
- Right boundary reversed (excl. root+leaf): [3]
```

**Example 2:**
```
Input: root = [5, null, 8, null, null, 6, 9]
Output: [5, 6, 9, 8]
Explanation:
- Left boundary: [5] (root only, since no left child; root acts as left boundary start)
- Leaves: [6, 9]
- Right boundary reversed: [8]
```

Constraints

  • The number of nodes is in the range [1, 1000].
  • Node values are in the range [-1000, 1000].

Follow-up

Can you solve this in a single DFS pass by tagging each node as 'left boundary', 'right boundary', or 'leaf' before traversal?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.