DSA sheet · Trees · DFS pattern

Boundary Traversal

Walk around the outside edge of a tree, anticlockwise: down the left edge, along the bottom (all the leaves), then up the right edge. The teacher calls this a very important interview question. Her approach breaks the big task into three small helpers: one collects the left edge, one collects the leaves, one collects the right edge (in reverse). The root is handled on its own first, so it isn't counted twice. Each helper is simple. The real learning is in the small conditions: why leaves are skipped on the edges, why we go right only when there's no left, and why the right edge must be reversed.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What "boundary" means and the plan
• Part A · Piece 1: the left boundary
• Part B · Piece 2: the leaf nodes
• Part C · Piece 3: the right boundary (reversed)
• Part D · Putting it together
• Part E · Revision page

Part 0 · Before starting

Words we will use

The teacher's tree

             1              ← root
           /   \
          2     3           ← 2 is on the left edge, 3 on the right edge
         / \   / \
        4   5 6   7         ← 4, 6, 7 are leaves
           / \
          8   9             ← 8, 9 are leaves

• Root: 1
• Left boundary (non-leaf nodes on the left edge): 2. (4 is on the left edge too, but it's a leaf, so it is counted with the leaves.)
• Leaves from left to right: 4, 8, 9, 6, 7
• Right boundary (non-leaf nodes on the right edge), read bottom to top: 3. (1 is the root, already counted. 7 is a leaf.)

Answer: 1 2 4 8 9 6 7 3. Trace it with your finger: down the left, along the bottom, up the right.

        start → 1
               ↙   ↖
              2     3         ← going up the right side at the end
             ↓       ↑
            4 → 8 → 9 → 6 → 7   (bottom row, left to right)

The plan: three helpers + the root

The teacher's first thought is "one function for the left side, one for the leaves, one for the right side". Then she notices a problem: the root sits at the top of both the left edge and the right edge, so it would be added twice. Her fix: handle the root separately, then start the left helper from root.left and the right helper from root.right.

1. If the root is not a leaf, add the root.
2. Add the left boundary, starting at root.left.
3. Add all leaves, searching from root.
4. Add the right boundary, starting at root.right, reversed.

All three helpers use one tiny check:

def is_leaf(node):
    return node.left is None and node.right is None

Part A · Piece 1: the left boundary

GFG · Boundary Traversal of Binary Tree

1The question in simple words

Starting from the root's left child, walk down the left edge of the tree and collect every node on it that is not a leaf, top to bottom.

2What the constraints tell us

• Number of nodes: 1 to 10⁵. The root always exists, but root.left may not, so the helper must handle a None start.
• 10⁵ nodes means O(n²) would be 10¹⁰ operations, far above the ~10⁸ safe limit → TLE. We aim for linear time (n log n only if we needed sorting, which we don't).

3Intuition: what can you see from the left?

The left edge is the path you get by always stepping left. But if a node has no left child, its right child is now the outermost node on that level, so it becomes part of the edge. In the teacher's words: if the left is there, the right is hidden behind it. If the left is missing, the right becomes visible.

So we walk down one path, choosing left whenever we can, and right only when we must. We add each node we pass, unless it's a leaf.

4Building the conditions from examples

Condition 1: skip leaves

On the teacher's tree the walk is 2 → 4. 2 is not a leaf → add. 4 is a leaf → don't add.

Condition 2: go left if possible, else go right

The teacher changes the tree: remove 4.

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

Now 2 has no left child. Looking from the left, you'd see 2, then 5, then 8. So the walk is 2 → 5 → 8: at 2 we must step right, because there is no left.

• 2: not a leaf → add. No left child → step right to 5.
• 5: not a leaf → add. Has a left child → step left to 8.
• 8: leaf → don't add. No children → we step to None and stop.

Left boundary = 2, 5, and the full answer for this tree becomes 1 2 5 8 9 6 7 3.

Condition 3: stop when we fall off the tree

The loop runs while node is not None. Stepping past a leaf gives None, and that ends the walk. The same check covers the case where the root has no left child at all: the loop never starts and the left boundary is empty.

5Approach steps

1. Start with node = root.left.
2. While node is not None:
3. If it's not a leaf, add node.val.
4. If it has a left child, move left. Otherwise move right.

6Code (Python)

def left_boundary(node, ans):
    while node:                         # stop when we fall off the tree
        if not is_leaf(node):           # leaves are added by leaf_nodes
            ans.append(node.val)
        if node.left:                   # left is the outer side
            node = node.left
        else:                           # no left -> right becomes the edge
            node = node.right

7Code line by line

8Dry run

9Complexity & remember

• Time O(h), where h is the height of the tree. We visit one node per level, because we never go down both sides. The teacher calls this log n, which is right for a balanced tree. For a skewed (line-shaped) tree, h can be n.
• Space O(1) extra: just one pointer (the answer list is output).

Part B · Piece 2: the leaf nodes

1The question in simple words

Collect every leaf of the whole tree, in order from left to right.

2What the constraints tell us

• Same constraints as Part A. Leaves can be anywhere, so we must look at every node → O(n), which is fine.
• This helper is recursive, so it needs a None base case to stop.
• Python note: for a line-shaped tree of 10⁵ nodes the recursion becomes 10⁵ calls deep, past Python's default limit (~1000). Raise it with sys.setrecursionlimit if needed.

3Intuition

DFS that always goes left before right visits leaves exactly in left-to-right order. So: visit every node; if it's a leaf, write it down; otherwise go into its left child, then its right child.

Why we pass the root here (not root.left)

Leaves can be on both sides of the root, so we search the whole tree from root. And if the root itself is a leaf (a one-node tree), this is the helper that adds it.

4Conditions

• node is None → return. Nothing here.
• is_leaf(node) → add its value and return (a leaf has no children to visit).
• Otherwise → leaf_nodes(node.left), then leaf_nodes(node.right). Left first keeps the left-to-right order.

5Approach steps

1. If the node is None, return.
2. If it's a leaf, add it and return.
3. Recurse left, then recurse right.

6Code (Python)

def leaf_nodes(node, ans):
    if node is None:                    # base case
        return
    if is_leaf(node):
        ans.append(node.val)
        return
    leaf_nodes(node.left, ans)          # left first -> left-to-right order
    leaf_nodes(node.right, ans)

7Code line by line

8Dry run with the call stack

1. 1: not a leaf → go left.
2. 2: not a leaf → go left.
3. 4: leaf → add 4. Return to 2.
4. 2 goes right: 5: not a leaf → go left: 8: leaf → add 8. Back to 5, go right: 9: leaf → add 9.
5. 5 returns, 2 returns. 1 goes right: 3: not a leaf → left 6: leaf → add 6. Right 7: leaf → add 7.
6. Everything returns. Leaves = 4, 8, 9, 6, 7.

The stack never holds more than one node per level at a time: 1, 2, 5, 8. Only after 8 is removed does 9 go on.

9Complexity & remember

• Time O(n): every node is visited once to check whether it's a leaf.
• Space O(h): the call stack, one node per level of the current path. log n for a balanced tree, n for a skewed one.

Part C · Piece 3: the right boundary (reversed)

1The question in simple words

Starting from the root's right child, walk down the right edge and collect every non-leaf node. But the boundary goes up the right side, so these nodes must appear bottom to top in the answer.

2What the constraints tell us

• Same as Part A. root.right may be None, so the walk must handle a None start.

3Intuition: mirror of the left boundary, plus a flip

It's the left-boundary walk seen in a mirror: prefer right, and go left only if there's no right child. The walk naturally goes top to bottom, but we need bottom to top. So we collect the nodes in a stack first, then pop them into the answer. Popping a stack gives the last item first, which reverses the order.

4Building the conditions from examples

Why we need the reverse: the teacher's extra example

On the teacher's tree, the right walk is 3 → 7, and 7 is a leaf, so only 3 is collected. With one node, you can't tell whether the order needs reversing. So she adds a child under 7 (we call it 10):

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

• Walk: 3 (not a leaf) → right 7 (now not a leaf) → right 10 (leaf, skip) → None.
• Top to bottom we collected 3, 7.
• Going anticlockwise, after the leaves (… 6, 10) we climb up: 7 first, then 3.

So the right boundary must be added reversed: 7, 3. The full answer for this tree: 1 2 4 8 9 6 10 7 3.

The move rule is mirrored

5Approach steps

1. Start with node = root.right and an empty stack.
2. While node: if it's not a leaf, push its value. Move right if possible, else left.
3. While the stack isn't empty: pop and add to the answer.

6Code (Python)

def right_boundary(node, ans):
    stack = []                          # collects top-to-bottom
    while node:
        if not is_leaf(node):
            stack.append(node.val)
        if node.right:                  # right is the outer side here
            node = node.right
        else:
            node = node.left
    while stack:                        # pop = bottom-to-top
        ans.append(stack.pop())

7Code line by line

8Dry run (the tree with 10 under 7)

1. node = 3: not a leaf → push 3. Has right → go to 7. stack: [3]
2. node = 7: not a leaf (it has 10) → push 7. Has right → go to 10. stack: [3, 7]
3. node = 10: leaf → skip. No right → go left → None. Loop ends.
4. Pop 7 → answer gets 7. Pop 3 → answer gets 3. Right boundary added: 7, 3 ✓

9Complexity & remember

• Time O(h): one node per level on the way down, and each pushed node is popped once.
• Space O(h): the stack holds at most one node per level.

Part D · Putting it together

1The question in simple words

Return root, then left boundary, then leaves, then the reversed right boundary, with every boundary node appearing exactly once.

2What the constraints tell us

• n ≥ 1, but we still return [] for an empty root, as a guard (the teacher does too).
• Linear time is needed, and we'll get it: O(h) + O(n) + O(h).

3Intuition: who owns which node

No node is owned twice, so no node is printed twice.

4The two root conditions

Why "add the root only if it's not a leaf"?

Take a tree with just one node, 1. It is the root and a leaf. If the main function added it, and then leaf_nodes(root) found it as a leaf, we'd get [1, 1] ✗. So the main function skips a leaf root and lets the leaf helper add it → [1] ✓. Both boundary helpers get None and add nothing.

Why the order of the calls matters

The answer is built by appending, so the calls must run in the anticlockwise order: left boundary → leaves → right boundary. Calling the right helper before the leaves would put 3 before 4.

5Approach steps

1. If root is None, return [].
2. If root is not a leaf, add root.val.
3. left_boundary(root.left, ans)
4. leaf_nodes(root, ans)
5. right_boundary(root.right, ans)
6. Return ans.

6Code (Python), the full solution

def is_leaf(node):
    return node.left is None and node.right is None

def left_boundary(node, ans):
    while node:
        if not is_leaf(node):
            ans.append(node.val)
        if node.left:
            node = node.left
        else:
            node = node.right

def leaf_nodes(node, ans):
    if node is None:
        return
    if is_leaf(node):
        ans.append(node.val)
        return
    leaf_nodes(node.left, ans)
    leaf_nodes(node.right, ans)

def right_boundary(node, ans):
    stack = []
    while node:
        if not is_leaf(node):
            stack.append(node.val)
        if node.right:
            node = node.right
        else:
            node = node.left
    while stack:
        ans.append(stack.pop())

def boundaryTraversal(root):
    ans = []
    if root is None:
        return ans
    if not is_leaf(root):               # root once, unless it is a leaf
        ans.append(root.val)
    left_boundary(root.left, ans)       # 1. down the left edge
    leaf_nodes(root, ans)               # 2. along the bottom
    right_boundary(root.right, ans)     # 3. up the right edge
    return ans

7Code line by line (main function)

8Dry run on the teacher's tree

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

1. Root 1 is not a leaf → ans = [1].
2. Left boundary from 2: 2 added; 4 is a leaf, skipped → ans = [1, 2].
3. Leaves from 1: 4, 8, 9, 6, 7 → ans = [1, 2, 4, 8, 9, 6, 7].
4. Right boundary from 3: stack [3]; 7 is a leaf, skipped → pop 3 → ans = [1, 2, 4, 8, 9, 6, 7, 3].
5. Final: 1 2 4 8 9 6 7 3 ✓

9Complexity & remember

• Time O(n). Root: O(1). Left boundary: one node per level, O(h). Leaves: every node, O(n). Right boundary: O(h). Total O(1) + O(h) + O(n) + O(h), and the O(n) term is the biggest, so O(n). (The teacher writes 2·log n + n, using h = log n for a balanced tree.)
• Space O(h): the recursion stack of the leaf helper and the right-boundary stack each hold at most one node per level. That's log n for a balanced tree, as the teacher says, and up to n for a skewed tree.

Part E · Revision page

t = TreeNode(1,
      TreeNode(2, TreeNode(4), TreeNode(5, TreeNode(8), TreeNode(9))),
      TreeNode(3, TreeNode(6), TreeNode(7)))
no4 = TreeNode(1,
        TreeNode(2, None, TreeNode(5, TreeNode(8), TreeNode(9))),
        TreeNode(3, TreeNode(6), TreeNode(7)))
print(boundaryTraversal(t))            # [1, 2, 4, 8, 9, 6, 7, 3]
print(boundaryTraversal(no4))          # [1, 2, 5, 8, 9, 6, 7, 3]
print(boundaryTraversal(TreeNode(1)))  # [1]

Based on this video: Boundary Traversal of Binary Tree