Outline of the Tree
MediumTrees
Problem
Trace the outline of a binary tree anticlockwise, starting at the root, and return the values met along the way. The outline is the concatenation of:
1. The root. 2. The left edge: start at root.left and repeatedly move to the left child, or to the right child when there is no left child; stop before reaching a leaf. Empty if the root has no left child. 3. All leaves from left to right. 4. The right edge, defined symmetrically from root.right (prefer the right child, else the left), excluding leaves, listed bottom-up.
Each node appears at most once; in particular a root that is itself a leaf is listed once.
Example 1
- Input:
- root = [1, null, 2, 3, 4]
- Output:
- [1, 3, 4, 2]
No left edge; leaves 3 and 4; the right edge is just 2.
Example 2
- 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]
Constraints
- 0 ≤ number of nodes ≤ 10^4
- Tree height ≤ 500
- -1000 ≤ node.val ≤ 1000
Hint
Show the first hint
Split the outline into three independent pieces and compute each one separately.
Walkthrough
How to approach it
01Clarify before coding
- Can the edges detour? Yes: when the edge node has no preferred child, it continues through the other one.
- Is the root a leaf when it has no children? Yes, and then the answer is just [root].
- Right edge order? Bottom-up, so the outline reads anticlockwise.
02Brute force
Compute the leftmost and rightmost node of every level and merge them with the bottom level.
Cost: O(n), but it is a different definition: it includes nodes that are not on the edge walk and misses leaves on inner levels.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.