Boundary of Binary Tree

MediumTreesdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given the root of a non-empty binary tree, return the values on its **boundary** in anti-clockwise order starting at the root. The boundary is the concatenation of four parts, with no node listed twice: 1. The **root**. 2. The **left boundary**: start at root.left (empty if the root has no left child). From each boundary node move to its left child if it exists, otherwise to its right child; stop when you reach a leaf. Leaves are excluded from this part. 3. The **leaves** of the whole tree, from left to right. The root is never treated as a leaf. 4. The **right boundary** in **reverse** (bottom-up): defined like the left boundary but starting at root.right and preferring right children. Leaves are excluded. A tree with a single node therefore returns just [root.val].

Examples

Input: root = [1,null,2,3,4]
Output: [1,3,4,2]
No left child, so the left boundary is empty. Leaves are 3 and 4, and the right boundary is just 2.
Input: root = [1,2,3,4,5,6,null,null,null,7,8,9,10]
Output: [1,2,4,7,8,9,10,6,3]
Left boundary is 2 (4 is a leaf). Leaves are 4, 7, 8, 9, 10. The right boundary is 3 then 6 (3 has no right child), reversed to 6, 3.

Constraints

  • 1 <= number of nodes <= 10^4
  • -1000 <= Node.val <= 1000

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems