Acrobats From the Wings
A circus troupe builds a human tower. One acrobat stands on the floor, and every acrobat can hold up to two others on their shoulders, one on the left shoulder and one on the right. Each acrobat wears a number, and the tower is recorded as a binary tree: the floor acrobat is the root, and a node's children are the acrobats on their shoulders.
The stage manager stands in the right-hand wing, looking across the stage at the tower. On each row of the tower, the manager can only see the acrobat nearest the right wing; everyone else on that row is hidden behind them. The lighting cue sheet needs exactly the numbers the manager can see.
Your task
Write seenFromWing(root). For each level of the tree, take the rightmost node on that level. Return their values starting with the root's level (the acrobat on the floor) and moving up one row at a time.
An empty tree gives an empty list. Trees are shown in level order, like [7, 3, 9, 1, 5], where null marks a missing child. Your function receives real TreeNode objects with val, left and right.
seenFromWing(root: TreeNode) → int[]
Examples
root = [7, 3, 9, 1, 5, null, null, null, null, 4]
[7, 9, 5, 4]
Row 1 is just 7. Row 2 is 3 and 9; 9 is nearest the wing. Row 3 is 1 and 5, both on 3's shoulders, because 9 holds nobody; 5 is visible. Row 4 is only 4, standing on 5. Following right shoulders alone would stop after 7 and 9 and miss 5 and 4.
root = [1, 2, 3, 4]
[1, 3, 4]
Row 2 shows 3. Row 3 has only acrobat 4, on the far left of the tower, but nobody stands to its right on that row, so the manager sees it.
Constraints
- 0 ≤ number of acrobats ≤ 1,000
- -100,000 ≤ number worn ≤ 100,000
- The tree is at most 500 levels deep.
Start with brute force
The quick guess is to walk down the right shoulders from the floor: root, root.right, root.right.right, and so on. It fails as soon as the right side of the tower is shorter than the left, as in the first example.
A correct slow fix is to compute, for each row number, every acrobat on that row by walking down from the root again, then pick the rightmost. Starting a fresh walk for each of up to 500 rows over 1,000 acrobats repeats a lot of work. One level-by-level pass finds every row at once.
Hints
0 of 4 shown- Hint 1
In the first example, the visible acrobat on row 3 stands on the left acrobat of row 2. So what decides who is visible: their position under their parent, or something about their whole row?
- Hint 2
Visibility depends only on the row. If you had all acrobats of one row, in left-to-right order, the answer for that row is the last one.
- Hint 3
Which traversal hands you the tree one complete row at a time, left to right?
- Hint 4
Breadth-first search with a queue. At the start of each level, note how many nodes are in the queue. Process exactly that many, pushing left child then right child, and record the value of the last node you process on that level.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
"Rightmost on each row" is a question about rows, so walk the tree row by row. Build each row in left-to-right order and take its last node.
Trace [7, 3, 9, 1, 5, null, null, null, null, 4]:
- Row [7]. Last is 7. Next row: 7's children, [3, 9].
- Row [3, 9]. Last is 9. Next row: 3 gives 1 and 5, 9 gives nothing, so [1, 5].
- Row [1, 5]. Last is 5. Next row: only 5 has a child, so [4].
- Row [4]. Last is 4. No children, so stop. Answer
[7, 9, 5, 4].
Pushing the left child before the right child is what keeps each row in left-to-right order. Swap them and you get the view from the other wing.
function seenFromWing(root) {
const seen = [];
if (root === null) return seen;
let row = [root];
while (row.length > 0) {
seen.push(row[row.length - 1].val); // rightmost on this row
const next = [];
for (const node of row) { // build the row above, left to right
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
row = next;
}
return seen;
}from collections import deque
def seen_from_wing(root):
seen = []
if root is None:
return seen
queue = deque([root])
while queue:
size = len(queue) # nodes on this row
for i in range(size):
node = queue.popleft()
if i == size - 1: # last one is nearest the wing
seen.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return seenRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.