Print the boundary of an N-ary tree counterclockwise: root, left edge, leaves left to right, right edge going up. How do you avoid printing a node twice?
Predict first
What boundary does the three-part join print?
final class NNode {
let val: Int
var kids: [NNode]
init(_ v: Int, _ kids: [NNode] = []) { val = v; self.kids = kids }
}
func boundary(_ root: NNode) -> [Int] {
if root.kids.isEmpty { return [root.val] }
var left: [Int] = [], right: [Int] = [], leaves: [Int] = []
var n = root.kids.first
while let c = n, !c.kids.isEmpty { left.append(c.val); n = c.kids.first } // leftmost path, no leaf
n = root.kids.last
while let c = n, !c.kids.isEmpty { right.append(c.val); n = c.kids.last } // rightmost path, no leaf
func collect(_ x: NNode) {
if x.kids.isEmpty { leaves.append(x.val) } else { for k in x.kids { collect(k) } }
}
for k in root.kids { collect(k) }
return [root.val] + left + leaves + right.reversed() // counterclockwise
}
let tree = NNode(1, [NNode(2, [NNode(5), NNode(6)]), NNode(3), NNode(4, [NNode(7, [NNode(8), NNode(9)])])])
print(boundary(tree))
print(boundary(NNode(1)))
print(boundary(NNode(1, [NNode(2), NNode(3)])))- [1, 2, 5, 6, 3, 8, 9, 7, 4] / [1] / [1, 2, 3]
- [1, 2, 5, 6, 3, 8, 9, 4, 7] / [1] / [1, 2, 3]
- [1, 2, 5, 6, 3, 8, 9, 7, 4] / [] / [1, 2, 3]
Mental model. Walking around the outline of a tree seen from above: up the left side, along the bottom of the leaves, back up the right side, without crossing your own footprints.
Split the boundary into three disjoint parts and join them, so no node is printed twice. The left edge follows the first child down from the root and stops before the first leaf; the right edge follows the last child down, again excluding the leaf, and is printed reversed so it goes upward; the leaves come from a depth-first walk collected left to right. Output is [root] + left + leaves + right.reversed(). For the tree in the check that is [1, 2, 5, 6, 3, 8, 9, 7, 4]. O(n) time, O(h) for the recursion.
Duplicates are the difficulty. A leaf on the edge is already in the leaf list, which is why both edge loops stop at a leaf (!c.kids.isEmpty), and the root must not be repeated as a leaf when it has no children (handled by returning [root.val] early). Ask the interviewer what “left edge” means when a node has only a later child: this version always descends through the first child (a stricter reading descends through the first child that exists and continues). The question is reported for Uber (anonymous, unverified) and is easy to botch, so state your definition before coding.
Root, left edge, all leaves, then the right edge reversed; a lone root and a root with two leaves are handled.
Common traps
- Printing leaves that lie on an edge twice. Stop each edge before its leaf.
- Forgetting to reverse the right edge, which prints it downwards.
They might follow up with
- How does it differ for a binary tree? Same idea with left/right children; the edge follows left if it exists, otherwise right.
- What is the complexity? O(n) time and O(h) stack.
Related questions
- 29.2.4 Return the values you see when looking at a binary tree from its right side. How does a level-order walk give…
- 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.6 Recursively walk a folder tree to count files and bytes. Compare your own recursion with…
← Return the values you see when looking at a binary tree from its… Recursively walk a folder tree to count files and bytes. Compare your… →