PPractick

The problem

A tree-drawing app outlines a binary tree by tracing its boundary anticlockwise:

1. the root
2. the left boundary going down, meaning the path that always prefers the left child and only takes the right child when there's no left one
3. all the leaves, left to right
4. the right boundary going back up

Leaves are listed only once, and boundary nodes that are leaves appear only in the leaf part. Three simple walks, one for each part, produce the outline.

Example: [1, 2, 3, 4, 5, 6, 7, null, null, 8, 9] → [1, 2, 4, 8, 9, 6, 7, 3].

Function signature

vector<int> boundaryTraversal(TreeNode* root);

Test cases

Input (level order)	Output	Explanation
[1, 2, 3, 4, 5, 6, 7, null, null, 8, 9]	[1, 2, 4, 8, 9, 6, 7, 3]	Left 2; leaves 4 8 9 6 7; right 3
[1, null, 2, null, 3]	[1, 3, 2]	No left subtree, so no left boundary
[1, 2, null, 3, null, 4]	[1, 2, 3, 4]	A left chain: 4 is the only leaf
[1, 2, 3]	[1, 2, 3]	Both children are leaves
[1]	[1]	The root alone

(Confirm: the root is listed once even if it's a leaf; if the root has no left child, the left boundary is empty, and likewise on the right.)

How interviewers phrase it

• "Print the boundary nodes of a binary tree anticlockwise, starting from the root" (GeeksforGeeks "Boundary Traversal of binary tree"; LeetCode 545).

Clarifying questions to ask

1. How is the left boundary defined when a node has no left child? (Take its right child.)
2. Should leaves on the boundary be listed twice? (No.)
3. What happens if the root has no left subtree? (The left boundary is empty.)

Follow-ups to expect

1. "Why exclude leaves from the boundary walks?"
2. "How are the leaves collected in left-to-right order?"
3. "Why reverse the right boundary?"
4. "Can it be one DFS?"
5. "Complexity?"

Related questions

• Maximum Depth in BT Medium
• Check for balanced binary tree Medium
• Maximum path sum Medium
• Check if two trees are identical or not Medium
• Vertical Order Traversal Medium
• Right/Left View of Binary Tree Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in