Boundary Traversal of Binary Tree in DSA Python

Mental Model

We want to walk around the edges of a tree, collecting nodes on the left edge, the leaves, and the right edge in order.

Analogy: Imagine walking around the outside of a garden shaped like a tree, first along the left fence, then along the flowers at the bottom, and finally along the right fence back to the start.

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

Boundary: left edge (1,2,4), leaves (4,7,8,9), right edge (3,6)

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6 / \ / 7 8 9 Goal: Collect boundary nodes in anti-clockwise order

Goal: Collect nodes on the left edge top-down, then all leaves left to right, then right edge bottom-up without duplicates

Step 1: Add root node 1 to boundary

Boundary: [1]

Why: Root is always part of the boundary

Step 2: Traverse left boundary excluding leaves: add 2

Boundary: [1, 2]

Why: Left edge nodes are added top-down excluding leaves to avoid duplicates

Step 3: Add all leaf nodes from left to right: 4,7,8,9

Boundary: [1, 2, 4, 7, 8, 9]

Why: Leaves are collected separately to include all bottom nodes

Step 4: Traverse right boundary excluding leaves bottom-up: add 6, then 3

Boundary: [1, 2, 4, 7, 8, 9, 6, 3]

Why: Right edge nodes are added bottom-up excluding leaves to avoid duplicates

Result:

Boundary traversal: 1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3

Annotated Code

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

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

def add_left_boundary(root, boundary):
    curr = root.left
    while curr:
        if not is_leaf(curr):
            boundary.append(curr.val)  # add left boundary node
        if curr.left:
            curr = curr.left  # go left if possible
        else:
            curr = curr.right  # else go right

def add_leaves(root, boundary):
    if root is None:
        return
    if is_leaf(root):
        boundary.append(root.val)  # add leaf node
    else:
        add_leaves(root.left, boundary)  # traverse left subtree
        add_leaves(root.right, boundary)  # traverse right subtree

def add_right_boundary(root, boundary):
    curr = root.right
    stack = []
    while curr:
        if not is_leaf(curr):
            stack.append(curr.val)  # collect right boundary nodes
        if curr.right:
            curr = curr.right  # go right if possible
        else:
            curr = curr.left  # else go left
    while stack:
        boundary.append(stack.pop())  # add right boundary bottom-up

def boundary_traversal(root):
    if root is None:
        return []
    boundary = [root.val] if not is_leaf(root) else []  # root if not leaf
    add_left_boundary(root, boundary)
    add_leaves(root, boundary)
    add_right_boundary(root, boundary)
    return boundary

# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.right.left = Node(7)
root.left.right.right = Node(8)
root.right.right = Node(6)
root.right.right.left = Node(9)

result = boundary_traversal(root)
print(' -> '.join(map(str, result)))

boundary = [root.val] if not is_leaf(root) else []

Add root to boundary if it is not a leaf

curr = root.left while curr: if not is_leaf(curr): boundary.append(curr.val) if curr.left: curr = curr.left else: curr = curr.right

Traverse left boundary top-down excluding leaves

if is_leaf(root): boundary.append(root.val) else: add_leaves(root.left, boundary) add_leaves(root.right, boundary)

Add all leaf nodes from left to right

curr = root.right stack = [] while curr: if not is_leaf(curr): stack.append(curr.val) if curr.right: curr = curr.right else: curr = curr.left while stack: boundary.append(stack.pop())

Traverse right boundary bottom-up excluding leaves

Output

1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3

Complexity Analysis

Time: O(n) because we visit each node at most once during traversal

Space: O(n) for the output list and recursion stack in worst case

vs Alternative: Naive approach might check all nodes multiple times; this method visits nodes in a controlled way to avoid duplicates and extra passes

Edge Cases

Empty tree

Returns empty list as there are no nodes

DSA Python

if root is None:
    return []

Tree with only root node

Returns list with root value, added as leaf in add_leaves

DSA Python

if is_leaf(root):
    boundary.append(root.val)  # in add_leaves

Tree with only left or only right subtree

Left or right boundary functions handle missing sides gracefully without errors

DSA Python

while curr:
    ...

When to Use This Pattern

When asked to print or collect nodes around the edges of a binary tree in order, use boundary traversal to combine left edge, leaves, and right edge efficiently.

Common Mistakes

Mistake: Including leaf nodes twice by adding them in both left/right boundary and leaves
Fix: Exclude leaf nodes from left and right boundary traversals, add them only once in leaf collection

Mistake: Adding right boundary nodes top-down instead of bottom-up
Fix: Collect right boundary nodes in a stack and add them in reverse order after traversal

Summary

Collects the nodes on the boundary of a binary tree in anti-clockwise order.

Use when you need to print or process the outer edge nodes of a tree distinctly.

The key is to separate left boundary, leaves, and right boundary to avoid duplicates and maintain order.

Practice

1. What does the boundary traversal of a binary tree include?

easy

A. Left boundary, leaves, and right boundary nodes

B. Only leaf nodes

C. Only root node

D. All nodes in level order

Solution

1. Step 1: Understand boundary traversal components

   Boundary traversal includes nodes on the left edge, all leaf nodes, and nodes on the right edge of the tree.

2. Step 2: Compare options with definition

   Only Left boundary, leaves, and right boundary nodes correctly lists left boundary, leaves, and right boundary nodes.

3. Final Answer:

   Left boundary, leaves, and right boundary nodes -> Option A

4. Quick Check:

   Boundary traversal = left boundary + leaves + right boundary [OK]

Hint: Remember boundary = left edge + leaves + right edge [OK]

Common Mistakes:

• Confusing boundary traversal with level order traversal
• Ignoring leaf nodes in boundary traversal
• Including all nodes instead of just edges and leaves

2. Which of the following is the correct Python function signature for boundary traversal of a binary tree?

easy

A. def boundaryTraversal(root, result):

B. def boundaryTraversal(root, left, right):

C. def boundaryTraversal():

D. def boundaryTraversal(root):

Solution

1. Step 1: Identify typical function signature

   Boundary traversal usually takes the root node as input and returns the traversal list.

2. Step 2: Check options for correct signature

   def boundaryTraversal(root): takes only root as input, which is standard and sufficient.

3. Final Answer:

   def boundaryTraversal(root): -> Option D

4. Quick Check:

   Function signature with root only is correct [OK]

Hint: Boundary traversal function needs only root parameter [OK]

Common Mistakes:

• Adding unnecessary parameters like left and right
• Missing root parameter
• Using empty parameter list

3. What is the output of the boundary traversal for the following binary tree?

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

medium

A. [1, 2, 4, 7, 8, 9, 6, 3]

B. [1, 2, 4, 7, 8, 9, 6]

C. [1, 4, 7, 8, 9, 6, 3]

D. [1, 2, 5, 7, 8, 9, 6, 3]

Solution

1. Step 1: Identify left boundary nodes

   Left boundary nodes are 1, 2, 4 (excluding leaf duplicates).

2. Step 2: Identify leaf nodes

   Leaves are 4, 7, 8, 9, 6.

3. Step 3: Identify right boundary nodes

   Right boundary nodes are 3, 6 (excluding leaf duplicates), so only 3.

4. Step 4: Combine nodes in order

   Boundary traversal = left boundary (1,2,4) + leaves (7,8,9,6) + right boundary reversed (3) = [1, 2, 4, 7, 8, 9, 6, 3]

5. Final Answer:

   [1, 2, 4, 7, 8, 9, 6, 3] -> Option A

6. Quick Check:

   Boundary traversal output matches [1, 2, 4, 7, 8, 9, 6, 3] [OK]

Hint: List left boundary, leaves, then right boundary reversed [OK]

Common Mistakes:

• Including leaf nodes twice in boundary
• Missing right boundary node 3
• Incorrect order of nodes

4. The following code attempts boundary traversal but misses some nodes. What is the bug?

def boundaryTraversal(root):
    result = []
    def leftBoundary(node):
        if node and (node.left or node.right):
            result.append(node.val)
            if node.left:
                leftBoundary(node.left)
            else:
                leftBoundary(node.right)
    def leaves(node):
        if node:
            leaves(node.left)
            if not node.left and not node.right:
                result.append(node.val)
            leaves(node.right)
    def rightBoundary(node):
        if node and (node.left or node.right):
            if node.right:
                rightBoundary(node.right)
            else:
                rightBoundary(node.left)
            result.append(node.val)
    if root:
        result.append(root.val)
        leftBoundary(root.left)
        leaves(root.left)
        leaves(root.right)
        rightBoundary(root.right)
    return result

medium

A. Leaves function misses leaf nodes on right subtree

B. Right boundary nodes are appended before recursive call

C. Left boundary includes leaf nodes causing duplicates

D. Root node is not added to result

Solution

1. Step 1: Analyze leftBoundary function

   Left boundary adds nodes with children but does not exclude leaf nodes explicitly, so leaf nodes can be added twice.

2. Step 2: Check leaves and rightBoundary functions

   Leaves function correctly adds leaf nodes; rightBoundary appends after recursion, which is correct.

3. Step 3: Identify bug

   Left boundary includes leaf nodes causing duplicates in result.

4. Final Answer:

   Left boundary includes leaf nodes causing duplicates -> Option C

5. Quick Check:

   Left boundary must exclude leaves to avoid duplicates [OK]

Hint: Exclude leaf nodes from left boundary to avoid duplicates [OK]

Common Mistakes:

• Appending right boundary nodes before recursion
• Not adding root node
• Leaves function missing some leaves

5. Given a binary tree where some nodes have only one child, how should the boundary traversal handle nodes with a single child to ensure all boundary nodes are included exactly once?

hard

A. Skip nodes with only one child in boundary traversal

B. Traverse left boundary by always choosing left child if present, else right child; similarly for right boundary, choose right child if present, else left child

C. Include all nodes regardless of position to avoid missing any

D. Only include leaf nodes and root node in boundary traversal

Solution

1. Step 1: Understand boundary traversal with single-child nodes

   When a node has only one child, boundary traversal must follow that child to include all boundary nodes.

2. Step 2: Apply traversal rules

   For left boundary, choose left child if exists; if not, choose right child. For right boundary, choose right child if exists; if not, choose left child.

3. Step 3: Avoid duplicates by excluding leaves in boundary functions

   Leaves are handled separately to avoid duplicates.

4. Final Answer:

   Traverse left boundary by always choosing left child if present, else right child; similarly for right boundary, choose right child if present, else left child -> Option B

5. Quick Check:

   Follow child presence rules to cover all boundary nodes [OK]

Hint: Choose child present on boundary side to cover all nodes [OK]

Common Mistakes:

• Skipping single-child nodes causing missing boundary nodes
• Including all nodes causing duplicates
• Ignoring leaf nodes in traversal