Skip to content
Onsite
14 / 29

Boundary Traversal of Binary Tree

MediumP3Coding

Return the boundary of a binary tree, anti-clockwise, starting at the root. The boundary is, in order:

  1. the root;
  2. the left boundary: from the root's left child, repeatedly go to the left child, or to the right child when there is no left child, stopping before a leaf (leaves are not part of this list);
  3. all leaves, from left to right;
  4. the right boundary: the mirror of the left boundary (right child preferred, then left), stopping before a leaf, listed from bottom to top.

A node never appears twice. The root is not a leaf even when it has no children; a single-node tree returns just that node. An empty tree returns [].

Example 1

Input
root = [1,null,2,3,4]
Output
[1,3,4,2]
Why
The root has no left child, so the left boundary is empty. Leaves are 3 and 4. The right boundary is 2.

Example 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]

Constraints

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

Hints

Run checks the 3 visible tests, Submit all 9.