AlgoViz
HomeBinary Trees

Boundary Traversal

Medium

Left edge, leaves, right edge reversed

Problem

Return the anticlockwise boundary of a binary tree: left boundary, leaves, then right boundary reversed.

In simple words

Walk the left boundary down, collect all leaves, then the right boundary up — the outline of the tree.

The idea

Assemble the outline from three walks: down the left boundary excluding leaves, across all the leaves left to right, and up the right boundary excluding leaves. Excluding leaves from the two edges is what stops corner nodes appearing twice.

The trick

  • Collect the right boundary top-down then reverse it.
  • Exclude leaves from both edge walks; the leaf pass covers them.
  • The root is included once, at the start.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
4
5
6
7
0
1
2
3
4
5
6

Step 1 of 2. Here's the example — [1,2,3,4,5,6,7] Values: 1, 2, 3, 4, 5, 6, 7.

1/2
Optimal
timeO(n)spaceO(h)
1add left boundary (top-down, exclude leaves)2add all leaves (left to right)3add right boundary (bottom-up, exclude leaves)

Input

array
[1, 2, 3, 4, 5, 6, 7]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
tree = [1,2,3,4,5,6,7]
Output:
[1, 2, 4, 5, 6, 7, 3]
Explanation:
Left edge, then leaves, then right edge (reversed).

Example 2

Input:
tree = [1,2,3]
Output:
[1, 2, 3]
Explanation:
Root, left leaf, right leaf.

Example 3

Input:
tree = [1]
Output:
[1]
Explanation:
Only the root.

Practice this problem:LeetCode (premium)(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.