Boundary Traversal of Binary Tree in DSA Python - Execution Trace

Concept Flow - Boundary Traversal of Binary Tree

Start at root

↓

Add root to boundary

↓

Traverse left boundary down (excluding leaves)

↓

Traverse all leaves from left to right

↓

Traverse right boundary up (excluding leaves)

↓

Combine all parts for final boundary traversal

The traversal collects nodes from the left boundary top-down, then all leaves left to right, then right boundary bottom-up, starting from the root.

Execution Sample

DSA Python

def boundaryTraversal(root):
    if not root:
        return []
    res = [root.val]
    # left boundary
    # leaves
    # right boundary
    return res

This code collects the boundary nodes of a binary tree in anti-clockwise order.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Boundary Nodes Collected)
1	Start at root	1	root points to node 1	[1]
2	Traverse left boundary down	2	current moves from 1 to 2	[1, 2]
3	Traverse left boundary down	4	current moves from 2 to 4	[1, 2, 4]
4	Left boundary ends (leaf node 4)	4	stop left boundary traversal	[1, 2, 4]
5	Traverse leaves left to right	4	leaf node found	[1, 2, 4]
6	Traverse leaves left to right	5	leaf node found	[1, 2, 4, 5]
7	Traverse leaves left to right	7	leaf node found	[1, 2, 4, 5, 7]
8	Traverse leaves left to right	8	leaf node found	[1, 2, 4, 5, 7, 8]
9	Traverse right boundary up	3	current moves from 1 to 3	[1, 2, 4, 5, 7, 8]
10	Traverse right boundary up	6	current moves from 3 to 6	[1, 2, 4, 5, 7, 8, 6]
11	Right boundary ends (leaf node 6)	6	stop right boundary traversal	[1, 2, 4, 5, 7, 8, 6]
12	Combine all parts	N/A	final boundary list ready	[1, 2, 4, 5, 7, 8, 6]

💡 All boundary nodes collected: left boundary, leaves, right boundary combined.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 10	Final
res (boundary list)	[]	[1, 2]	[1, 2, 4]	[1, 2, 4, 5, 7, 8]	[1, 2, 4, 5, 7, 8, 6]	[1, 2, 4, 5, 7, 8, 6]
current (left boundary)	root (1)	2	4	N/A	N/A	N/A
current (right boundary)	N/A	N/A	N/A	N/A	3	6

Key Moments - 3 Insights

Why do we exclude leaf nodes when traversing left and right boundaries?

Because leaf nodes are collected separately in the leaves traversal step to avoid duplicates, as shown in steps 4 and 11 where traversal stops before adding leaf nodes again.

How do we ensure leaves are collected from left to right?

We perform a full tree traversal (inorder or preorder) to visit all leaves in left-to-right order, as seen in steps 5 to 8 where leaves 4, 5, 7, and 8 are added sequentially.

Why is the right boundary added in reverse order?

Because the boundary traversal is anti-clockwise, the right boundary nodes are collected bottom-up after leaves, as shown in steps 9 to 11 where nodes 3 and 6 are added after leaves.

Visual Quiz - 3 Questions

Look at the execution table, what nodes are in the boundary list after step 7?

A [1, 2, 4, 5]

B [1, 2, 4]

C [1, 2, 4, 5, 7, 8]

D [1, 2, 4, 5, 7]

💡 Hint

Check the 'Tree State' column at step 7 in the execution table.

At which step does the left boundary traversal stop because it reaches a leaf node?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for the step where 'Left boundary ends (leaf node 4)' is noted in the execution table.

If the tree had no right subtree, how would the boundary list change after step 10?

A It would be the same as after step 7

B It would include extra right boundary nodes

C It would be empty

D It would only contain leaves

💡 Hint

Refer to the variable_tracker for 'res' and consider no right boundary nodes added.

Concept Snapshot

Boundary Traversal of Binary Tree:
- Start at root, add root to result
- Traverse left boundary top-down (exclude leaves)
- Traverse all leaves left to right
- Traverse right boundary bottom-up (exclude leaves)
- Combine all for final boundary list
- Avoid duplicates by excluding leaves in boundaries

Full Transcript

Boundary traversal collects nodes on the outer edge of a binary tree in anti-clockwise order. It starts at the root, then moves down the left boundary excluding leaves, collects all leaves from left to right, and finally moves up the right boundary excluding leaves. This ensures all boundary nodes are included without duplicates. The traversal stops left and right boundary collection at leaf nodes because leaves are handled separately. The final boundary list combines these parts to represent the tree's outer boundary.

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