Skip to main content

545. Boundary of Binary Tree

mediumAsked at Airbnb

Return the values on the boundary of a binary tree: left side top-down, leaves left-to-right, right side bottom-up. Airbnb asks this to test combining three different traversals without double-counting corners.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Airbnb loops.

  • Glassdoor (2026-Q1)— Airbnb onsite reports consistently list this as a signature tree medium.
  • Blind (2025-11)— Recurring in Airbnb new-grad and L4 interview reports.

Problem

The boundary of a binary tree is the concatenation of the root, the left boundary, the leaves ordered from left-to-right, and the reverse order of the right boundary. The left boundary is the set of nodes defined by the following: the root has a left boundary if it has a left child. Otherwise, the left boundary is empty. If a node in the left boundary and has a left child, then the left child is in the left boundary. If a node is in the left boundary, has no left child but has a right child, then the right child is in the left boundary. The leftmost leaf is not in the left boundary. The right boundary is similar to the left boundary, except it is the right side of the root's right subtree. Again, the leaf is not part of the right boundary, and the right boundary is empty if the root does not have a right child. The leaves are nodes that do not have any children. Given the root of a binary tree, return the values of its boundary.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4].
  • -1000 <= Node.val <= 1000

Examples

Example 1

Input
root = [1,null,2,3,4]
Output
[1,3,4,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]

Approaches

1. Three-pass traversal (optimal)

Walk left boundary (excluding leaves). Walk all leaves left-to-right. Walk right boundary (excluding leaves), then reverse. Concatenate with the root.

Time
O(n)
Space
O(n)
function boundaryOfBinaryTree(root) {
  if (!root) return [];
  const result = [root.val];
  function isLeaf(n) { return !n.left && !n.right; }
  function addLeft(node) {
    while (node) {
      if (!isLeaf(node)) result.push(node.val);
      node = node.left || node.right;
    }
  }
  function addLeaves(node) {
    if (!node) return;
    if (isLeaf(node)) { result.push(node.val); return; }
    addLeaves(node.left);
    addLeaves(node.right);
  }
  function addRight(node) {
    const stack = [];
    while (node) {
      if (!isLeaf(node)) stack.push(node.val);
      node = node.right || node.left;
    }
    while (stack.length) result.push(stack.pop());
  }
  if (isLeaf(root)) return result;
  addLeft(root.left);
  addLeaves(root.left);
  addLeaves(root.right);
  addRight(root.right);
  return result;
}

Tradeoff: Three clean phases: down the left edge (no leaves), DFS for all leaves, up the right edge (no leaves), reverse the right phase. Single-leaf root is the only base case.

Airbnb-specific tips

Airbnb's bar is naming the three sub-traversals and the no-double-count rule. Say: 'I split the boundary into three pieces — left edge top-down without leaves, all leaves left-to-right, right edge bottom-up without leaves. The root is added separately so corners aren't double-counted.' Without that decomposition, the code looks ad hoc.

Common mistakes

  • Including leaves in the left/right edge traversals (they get included in the leaf phase, so this double-counts).
  • Walking the left edge as 'always go left' — must fall back to right child if left is missing.
  • Single-leaf-root edge case (the leaf is the root; return [root.val] not [root.val, root.val]).

Follow-up questions

An interviewer at Airbnb may pivot to one of these next:

  • Right view / left view of a binary tree.
  • Top view / bottom view (LC 314 / column traversal).
  • What if the tree had cycles or back-pointers? (Different problem entirely.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the leftmost leaf NOT in the left boundary?

Convention from the problem statement. It IS in the leaves phase, so excluding it from the left boundary avoids double-counting.

What if root has only a right subtree?

Left boundary is empty. addLeft(root.left) is a no-op. The result starts with [root.val], then leaves, then the reversed right boundary.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Boundary of Binary Tree and other Airbnb interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →