Topics › Binary Trees › Medium Problems

Boundary Traversal

Medium TUF ID 116 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given the root of a binary tree, return the values on its boundary, walking anticlockwise from the root, with every node listed once. The boundary is made of four parts, in this order:

1. The root.
2. The left boundary, top-down: start at root.left; from each node move to its left child if it has one, otherwise to its right child; stop at a leaf. The leaf itself is not part of the left boundary. If the root has no left child, the left boundary is empty.
3. All leaves, from left to right.
4. The right boundary, bottom-up: defined like the left one but starting at root.right and preferring the right child; again excluding the leaf, and empty if the root has no right child.

Constraints: 0 ≤ n ≤ 10^4 nodes, values fit in an int. If the tree is a single node, the answer is just that node.

Example 1

tree (level order) = [1, 2, 3, 4, 5, 6, 7, null, null, 8, 9]

          1
        /   \
       2     3
      / \   / \
     4   5 6   7
        / \
       8   9

answer = [1, 2, 4, 8, 9, 6, 7, 3]
// root 1 | left boundary 2 | leaves 4 8 9 6 7 | right boundary (reversed) 3

Example 2

tree (level order) = [20, 8, 22, 4, 12, null, 25, null, null, 10, 14]

        20
       /  \
      8    22
     / \     \
    4   12    25
       /  \
      10   14

answer = [20, 8, 4, 10, 14, 25, 22]
// root 20 | left boundary 8 | leaves 4 10 14 25 | right boundary 22

The definition is designed so that the four parts never overlap: boundaries exclude leaves, the leaf list owns them, and the root is handled separately. Most bugs in this problem are double counting at the places where two parts meet, so the code is written to make those meeting points explicit.

Approach 1: Three separate walks

Intuition. Build the answer exactly as the definition reads, one part at a time.

• The left boundary is a single path, so a loop suffices: stand on root.left, record the node if it is not a leaf, step to the left child if it exists or else the right child, and stop when you fall off.
• The leaves in left-to-right order are what any depth-first traversal that visits the left subtree before the right one produces, keeping only the nodes with no children.
• The right boundary is the mirror-image loop, but it must come out bottom-up, so collect it top-down into a temporary list and append that list in reverse.

The root is added first only if it is not a leaf; a lone root is a leaf, and the leaf walk adds it, so it appears exactly once.

Algorithm.

1. If the tree is empty, return []. If the root is not a leaf, add it.
2. Walk the left boundary from root.left, adding non-leaf nodes.
3. Add all leaves with a recursive left-to-right DFS.
4. Walk the right boundary from root.right, collecting non-leaf nodes, and add them in reverse.

static List<Integer> threeParts(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    if (!isLeaf(root)) out.add(root.val);      // a lone root is added by the leaf walk instead
    addLeftBoundary(root, out);
    addLeaves(root, out);
    addRightBoundary(root, out);
    return out;
}

static void addLeftBoundary(TreeNode root, List<Integer> out) {
    TreeNode cur = root.left;
    while (cur != null) {
        if (!isLeaf(cur)) out.add(cur.val);
        cur = cur.left != null ? cur.left : cur.right;
    }
}

static void addLeaves(TreeNode node, List<Integer> out) {
    if (node == null) return;
    if (isLeaf(node)) {
        out.add(node.val);
        return;
    }
    addLeaves(node.left, out);
    addLeaves(node.right, out);
}

static void addRightBoundary(TreeNode root, List<Integer> out) {
    List<Integer> tmp = new ArrayList<>();
    TreeNode cur = root.right;
    while (cur != null) {
        if (!isLeaf(cur)) tmp.add(cur.val);
        cur = cur.right != null ? cur.right : cur.left;
    }
    for (int i = tmp.size() - 1; i >= 0; i--) out.add(tmp.get(i));   // bottom-up
}

Dry run on Example 2:

Result: [20, 8, 4, 10, 14, 25, 22].

Complexity. Time O(n): the leaf walk visits every node once and the two boundary walks follow one path each, O(h) steps. Space O(h) for the leaf recursion and the temporary right-boundary list.

Approach 2: One DFS with boundary flags

Intuition. The three parts can also be produced in one ordinary depth-first traversal (left subtree before right subtree) if every call knows whether its node lies on the left boundary or on the right boundary. Those flags can be passed down:

• root.left is on the left boundary. A left-boundary node’s left child is on the left boundary, and its right child is too, but only when there is no left child (the “otherwise go right” rule).
• Symmetrically for the right boundary: the right child always continues it, the left child only when there is no right child.

The traversal also gives us two natural moments to emit a node: before visiting its children (pre-order) and after (post-order). Left-boundary nodes are emitted pre-order, which lists them top-down. Right-boundary nodes are emitted post-order, which lists them bottom-up, so no reversal is needed. Every other leaf is emitted when it is reached; a DFS reaches leaves from left to right.

What about the leaves at the ends of the two boundaries? The left boundary ends at the leftmost leaf, the first leaf any left-first DFS meets, so emitting it as part of the boundary puts it exactly where it belongs: after the left boundary, before every other leaf. Likewise the right boundary ends at the rightmost leaf, the last leaf the DFS meets, emitted just before the post-order unwinding lists the rest of the right boundary. That is why the leaf check is !onRight && isLeaf(node) combined with onLeft ||: a boundary leaf is emitted by its boundary rule, and only once.

Algorithm.

1. If the tree is empty, return []. Add the root.
2. dfs(root.left, onLeft = true, onRight = false) and dfs(root.right, onLeft = false, onRight = true).
3. In dfs(node, onLeft, onRight):
   • before the children: emit the node if onLeft, or if it is a leaf and not onRight;
   • recurse left with (onLeft, onRight && node.right == null);
   • recurse right with (onLeft && node.left == null, onRight);
   • after the children: emit the node if onRight.

static List<Integer> singleDfs(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    out.add(root.val);
    dfs(root.left, true, false, out);
    dfs(root.right, false, true, out);
    return out;
}

static void dfs(TreeNode node, boolean onLeft, boolean onRight, List<Integer> out) {
    if (node == null) return;
    if (onLeft || (!onRight && isLeaf(node))) out.add(node.val);    // pre-order moment
    dfs(node.left, onLeft, onRight && node.right == null, out);
    dfs(node.right, onLeft && node.left == null, onRight, out);
    if (onRight) out.add(node.val);                                 // post-order moment
}

Complexity. Time O(n): one traversal. Space O(h) for the recursion. It is shorter than Approach 1 and needs no temporary list, at the cost of a subtler correctness argument; the Java file checks it against Approach 1 on 300 seeded random trees.

Edge cases and pitfalls

• Empty tree. Return an empty list.
• Single node. The root is also a leaf; print it once. Approach 1 skips the root when it is a leaf and lets the leaf walk add it; Approach 2 adds the root up front and never calls dfs on it.
• Missing subtree. If the root has no left child, the left boundary is empty, and leaves of the right subtree are still listed. In the right-skewed tree [1, null, 2, null, 3] the answer is [1, 3, 2]: root, leaf 3, then the right boundary 2.
• A boundary that turns. In [1, 2, 3, null, 4, null, null, 5, 6] the left boundary goes 2 -> 4 (no left child at 2), giving [1, 2, 4, 5, 6, 3]. In [1, null, 2, 3] the right boundary turns left at 2, giving [1, 3, 2].
• Double counting. Adding the leaf at the end of a boundary in both the boundary walk and the leaf walk, or adding a leaf root twice, are the two typical mistakes.
• Forgetting the reversal. The right boundary is read bottom-up. Appending it top-down produces a clockwise answer on that side.
• Check the definition. The rules for where a boundary turns and where it stops are part of the problem statement, not of the algorithm. The definition here matches the TUF sheet and LeetCode 545; if a judge disagrees on a tree where a boundary turns, compare its rules with the four parts above before debugging the code.

Related problems

• Right/Left View of Binary Tree lists the first or last node of every level, a different notion of “edge of the tree”.
• Top View of BT and Bottom view of BT look at the outline of the tree by column.
• Vertical Order Traversal assigns every node a column, the tool behind those views.
• Zig Zag or Spiral Traversal is another traversal with an unusual output order.