Boundary of Binary Tree

Boundary of Binary Tree

What is this problem about?

The Boundary of Binary Tree interview question asks you to return the values of the nodes that form the "boundary" of a binary tree in counter-clockwise order, starting from the root. The boundary consists of the root, the left boundary (excluding the leaf), all leaves from left to right, and the right boundary (excluding the leaf, in reverse order).

Why is this asked in interviews?

Companies like Microsoft, Amazon, and Meta use this problem to test your ability to decompose a complex task into smaller, manageable sub-problems. It requires a deep understanding of different tree traversal types and the ability to handle edge cases where the left or right boundary might not exist. It's an excellent test of code organization and recursion.

Algorithmic pattern used

This problem is best solved by breaking it into four distinct parts using Depth-First Search (DFS):

1. Root: Add the root value.
2. Left Boundary: Use a modified DFS to traverse down the left side, preferring the left child but taking the right child if the left is NULL. Exclude leaf nodes.
3. Leaves: Use a standard DFS (Pre-order or In-order) to find all leaf nodes and add them.
4. Right Boundary: Similar to the left boundary but in reverse order. Traverse down the right side (preferring right child) and use a stack or reverse the result at the end.

Example explanation

Consider this tree: 1 / 2 3 / \ / 4 5 6 / 7 8

1. Root: [1]
2. Left Boundary: Node 2 (Node 4 is a leaf, so skip). Result: [1, 2]
3. Leaves: 4, 7, 8, 6. Result: [1, 2, 4, 7, 8, 6]
4. Right Boundary: Node 3. Result: [1, 2, 4, 7, 8, 6, 3]

Common mistakes candidates make

The most common mistake is double-counting the root or the leaf nodes where the boundaries meet. Another error is failing to correctly traverse the "boundary" when a node only has a child on the "inner" side (e.g., a left boundary node that only has a right child). Handling the counter-clockwise requirement for the right boundary is also a frequent point of failure.

Interview preparation tip

Modularize your code. Write separate helper functions for getLeftBoundary, getLeaves, and getRightBoundary. This makes your code much easier to debug and demonstrates good engineering practices to the interviewer.