Skills101
← All coding problems

Boundary Traversal of Binary Tree

hardTrees & BST II+40 XPTime limit 2s

Trace the outline of a binary tree anticlockwise, starting at the root, and print every node on it exactly once. The outline has four parts, in this order:

  1. The root.
  2. The left boundary, top to bottom: start at the root's left child; from each node move to its left child if it has one, otherwise to its right child; stop when you reach a leaf. Leaves on this path are not printed here. (If the root has no left child, this part is empty.)
  3. All leaves, from left to right (the root itself does not count as a leaf).
  4. The right boundary, bottom to top: the mirror of part 2 — start at the root's right child, prefer the right child, then the left; again without leaves. (Empty if the root has no right child.)

Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is

    3
   / \
  9   20
     /  \
    15   7

Input: one tree.

Output: the boundary values on one line, or empty for an empty tree.

Constraints: 0 ≤ nodes ≤ 10⁴, −1000 ≤ value ≤ 1000. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.

Think about it: handle the three parts separately and glue them. The left and right boundaries are simple loops; the leaves come from any left-before-right traversal (preorder or inorder). The tricky cases are a root with only one child, and a boundary that ends in a leaf — that leaf must be printed once, in the leaves part.

Sample input 1

1 2 3 4 5 6 7 null null 8 9

Sample output 1

1 2 4 8 9 6 7 3

Sample input 2

1 null 2 3 4

Sample output 2

1 3 4 2

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.