Return the values you see when looking at a binary tree from its right side. How does a level-order walk give it, and what is the trap with a left-only branch?
Predict first
What do these three trees show from the right?
final class TreeNode {
let val: Int
var left: TreeNode?, right: TreeNode?
init(_ v: Int) { val = v }
}
func build(_ a: [Int?]) -> TreeNode? { // level-order, nil = missing child
guard let first = a.first, let f = first else { return nil }
let root = TreeNode(f)
var queue = [root], i = 1
while !queue.isEmpty && i < a.count {
let n = queue.removeFirst()
if i < a.count, let v = a[i] { n.left = TreeNode(v); queue.append(n.left!) }; i += 1
if i < a.count, let v = a[i] { n.right = TreeNode(v); queue.append(n.right!) }; i += 1
}
return root
}
func rightSide(_ root: TreeNode?) -> [Int] {
guard let root else { return [] }
var out: [Int] = []
var level = [root]
while !level.isEmpty {
out.append(level[level.count - 1].val) // the last node of each level is visible
level = level.flatMap { [$0.left, $0.right].compactMap { $0 } }
}
return out
}
print(rightSide(build([1, 2, 3, nil, 5, nil, 4])))
print(rightSide(build([1, 2, nil, 3]))) // only a left spine: still all visible
print(rightSide(build([])))- [1, 3, 4] / [1, 2, 3] / []
- [1, 3, 5] / [1, 2, 3] / []
- [1, 3, 4] / [1] / []
Mental model. Standing to the right of a hedge of different heights: from each row you see only the plant nearest you, and if that row has nothing on your side you see the one behind it.
The visible node at each depth is the last node of that level, so do a breadth-first traversal level by level and record the last value of each level. The program keeps the current level in an array: record its last element, then build the next level with flatMap over each node’s non-nil children, left before right so the rightmost stays last. O(n) time, O(w) memory for the widest level. A depth-first alternative visits right child first and records the first node it meets at each new depth.
The trap is a branch with no right child: if you only follow .right you miss nodes hidden behind a missing right side. In [1, 2, nil, 3] every node is visible, because 3 is the only node at its level, and the check prints [1, 2, 3]. Also handle the empty tree (return []) and build the test tree from a level-order array with nil for missing children, as the helper does. The variation “left view” just takes the first of each level, and “vertical order” needs a column index. Reported at Uber (anonymous, unverified).
The last node of each level is visible, including a node reached only through a left child.
Common traps
- Following only the right child. A node on the left can be the visible one at its depth.
- Recording the first element of each level (that is the left view).
They might follow up with
- Which traversal uses less memory on a very deep, thin tree? Depth-first: O(h) stack, while breadth-first holds a whole level.
- How do you serialise a tree for tests? Level-order with
nilfor gaps, as in the helper.
Related questions
- 29.2.3 Given a binary search tree and a decimal target, find the value closest to the target. Why can you stop…
- 29.2.5 Print the boundary of an N-ary tree counterclockwise: root, left edge, leaves left to right, right edge going…
- 29.2.1 Reverse a singly linked list in Swift, iteratively and recursively. What can go wrong with long lists?
← Given a binary search tree and a decimal target, find the value… Print the boundary of an N-ary tree counterclockwise: root, left… →