Walk Around the Outer Edge of the Tree
Solve this ProblemYou are given the root of a binary tree. List the nodes on its outer edge, going counter-clockwise, each node exactly once: first the root, then the left edge from top to bottom, then all the leaves from left to right, and finally the right edge from bottom to top. The left edge starts at the root's left child and always steps to the left child, or to the right child when there is no left child; the right edge is defined symmetrically. Leaves are never listed as part of an edge — they appear only in the leaves section.
The three parts can be produced by three separate walks, or by a single depth-first walk that remembers whether the current node lies on the left edge or the right edge.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; −100 ≤ node.val ≤ 100 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
Walk the outer edge counter-clockwise, each node once: (1) the root; (2) the LEFT EDGE from the root's left child downwards, always stepping to the left child when there is one, otherwise the right child, leaving out leaves; (3) ALL leaves from left to right; (4) the RIGHT EDGE, found the same way from the root's right child (right child preferred, otherwise left), leaving out leaves, listed from the bottom up - ◆
A single-node tree returns just that node. An empty tree returns an empty list
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Three Separate Walks: Left Edge, Leaves, Right Edge
GoodBuild the answer part by part, exactly as the definition says. After the root: follow the left edge with a loop (take the left child if present, otherwise the right child) and record each non-leaf node. Then a separate recursive pass records all the leaves from left to right. Finally follow the right edge with another loop (right child preferred), record its non-leaf nodes in a temporary list, and append that list reversed so the right edge reads from bottom to top. Three passes, each O(n) or less — O(n) time overall — and O(h) extra space for the recursion and the temporary right-edge list.
O(n)O(h)1class Solution {
2 public List<Integer> outerEdge(TreeNode root) {
3 List<Integer> out = new ArrayList<>();
4 if (root == null) return out;
5 out.add(root.val);
6 if (isLeaf(root)) return out;
7 TreeNode cur = root.left;
8 while (cur != null) {
9 if (!isLeaf(cur)) out.add(cur.val);
10 cur = cur.left != null ? cur.left : cur.right;
11 }
12 addLeaves(root, out);
13 List<Integer> rightSide = new ArrayList<>();
14 cur = root.right;
15 while (cur != null) {
16 if (!isLeaf(cur)) rightSide.add(cur.val);
17 cur = cur.right != null ? cur.right : cur.left;
18 }
19 Collections.reverse(rightSide);
20 out.addAll(rightSide);
21 return out;
22 }
23
24 private boolean isLeaf(TreeNode node) {
25 return node.left == null && node.right == null;
26 }
27
28 private void addLeaves(TreeNode node, List<Integer> out) {
29 if (node == null) return;
30 if (isLeaf(node)) {
31 out.add(node.val);
32 return;
33 }
34 addLeaves(node.left, out);
35 addLeaves(node.right, out);
36 }
37}Optimal — One Depth-First Pass Carrying "On the Left Edge / On the Right Edge" Flags
OptimalDo it in a single walk from the root's two children, passing two flags down: onLeft ("this node is on the left edge") and onRight. A leaf is recorded immediately — depth-first, left-first order visits leaves left to right. A node on the left edge is recorded on the way DOWN (pre-order, so the edge reads top to bottom, and it appears before any leaf below it), and a node on the right edge is set aside on the way down in a separate list that is reversed at the end (bottom to top). The flags are inherited carefully: the left child keeps "left edge", and the right child is on the left edge only if there is no left child; symmetrically for the right edge. One pass, O(n) time, O(h) space.
O(n)O(h)1class Solution {
2 public List<Integer> outerEdge(TreeNode root) {
3 List<Integer> out = new ArrayList<>();
4 if (root == null) return out;
5 out.add(root.val);
6 if (root.left == null && root.right == null) return out;
7 List<Integer> rightSide = new ArrayList<>();
8 walk(root.left, true, false, out, rightSide);
9 walk(root.right, false, true, out, rightSide);
10 Collections.reverse(rightSide);
11 out.addAll(rightSide);
12 return out;
13 }
14
15 private void walk(TreeNode node, boolean onLeft, boolean onRight, List<Integer> out, List<Integer> rightSide) {
16 if (node == null) return;
17 if (node.left == null && node.right == null) {
18 out.add(node.val);
19 return;
20 }
21 if (onLeft) out.add(node.val);
22 if (onRight) rightSide.add(node.val);
23 walk(node.left, onLeft, onRight && node.right == null, out, rightSide);
24 walk(node.right, onLeft && node.left == null, onRight, out, rightSide);
25 }
26}