Boundary Traversal of Binary Tree in DSA C - 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 left to right

↓

Traverse right boundary up (excluding leaves)

↓

Combine all parts for final boundary traversal

Start from root, add left boundary top-down, then leaves left to right, then right boundary bottom-up to get full boundary traversal.

Execution Sample

DSA C

void boundaryTraversal(Node* root) {
  if (!root) return;
  printf("%d ", root->data);
  printLeftBoundary(root->left);
  printLeaves(root->left);
  printLeaves(root->right);
  printRightBoundary(root->right);
}

This code prints the boundary nodes of a binary tree in order: root, left boundary, leaves, then right boundary.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Boundary Nodes Collected)
1	Start at root	1	root pointer set	[1]
2	Traverse left boundary down	2	move to left child	[1, 2]
3	Traverse left boundary down	4	move to left child	[1, 2, 4]
4	Traverse leaves	8	visit leaf	[1, 2, 4, 8]
5	Traverse leaves	9	visit leaf	[1, 2, 4, 8, 9]
6	Traverse leaves	5	visit leaf	[1, 2, 4, 8, 9, 5]
7	Traverse leaves	6	visit leaf	[1, 2, 4, 8, 9, 5, 6]
8	Traverse right boundary up	3	move to right child	[1, 2, 4, 8, 9, 5, 6, 3]
9	Traverse right boundary up	7	move to right child	[1, 2, 4, 8, 9, 5, 6, 3, 7]
10	Traverse right boundary up	10	move to right child	[1, 2, 4, 8, 9, 5, 6, 3, 7, 10]
11	End traversal	null	no more nodes	[1, 2, 4, 8, 9, 5, 6, 3, 7, 10]

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

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 9	Final
root	Node 1	Node 1	Node 1	Node 1	Node 1	Node 1
currentLeft	Node 2	Node 4	Node 4	Node 4	Node 4	null
currentRight	Node 3	Node 3	Node 3	Node 7	Node 10	null
boundaryList	[]	[1,2]	[1,2,4,8,9,5,6]	[1,2,4,8,9,5,6]	[1,2,4,8,9,5,6,3,7,10]	[1,2,4,8,9,5,6,3,7,10]

Key Moments - 3 Insights

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

Because leaf nodes are added separately during the leaf traversal step, including them in boundary traversal would cause duplicates. See execution_table steps 2-3 and 8-10 where leaves are excluded.

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

The leaf traversal visits all nodes in the tree in an in-order fashion, adding only leaves. This guarantees left-to-right order as shown in execution_table steps 4-7.

Why is the right boundary added in bottom-up order?

To maintain the correct boundary order, right boundary nodes are collected top-down but added to the boundary list in reverse (bottom-up). This is shown in execution_table steps 8-10.

Visual Quiz - 3 Questions

Look at the execution_table, which node is added first during the left boundary traversal?

A Node 4

B Node 2

C Node 1

D Node 8

💡 Hint

Check execution_table step 2 under 'Node Visited' during left boundary traversal.

At which step does the leaf node 5 get added to the boundary list?

A Step 6

B Step 4

C Step 5

D Step 7

💡 Hint

Look at execution_table steps 4-7 for leaf nodes added; node 5 is added at step 6.

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

A Left boundary would be empty

B Leaves would not be added

C Right boundary nodes would be missing, so fewer nodes in boundary list

D Root would not be added

💡 Hint

Refer to variable_tracker 'currentRight' variable and execution_table steps 8-10.

Concept Snapshot

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

Full Transcript

Boundary traversal of a binary tree collects nodes on the outer edge in a specific order. We start at the root and add it to the boundary list. Then we move down the left boundary, adding nodes except leaves. Next, we visit all leaf nodes from left to right. Finally, we traverse the right boundary from bottom to top, again excluding leaves. This order ensures all boundary nodes are included without duplicates. The execution table shows each step visiting nodes and updating the boundary list. Variables track current nodes on left and right boundaries and the growing boundary list. Key points include excluding leaves in boundary traversals to avoid duplicates and adding right boundary nodes in reverse order. The visual quiz tests understanding of node order and effects of missing subtrees.

Practice

1. What is the main purpose of the Boundary Traversal of Binary Tree?

easy

A. To print all nodes on the boundary of the tree in an anti-clockwise direction

B. To print all nodes in level order

C. To print all leaf nodes only

D. To print nodes in in-order traversal

Solution

1. Step 1: Understand boundary traversal definition

   Boundary traversal prints nodes on the edges of the tree: left boundary, leaves, and right boundary.

2. Step 2: Compare with other traversals

   Level order prints all nodes level-wise, leaf traversal prints only leaves, in-order prints nodes in left-root-right order.

3. Final Answer:

   To print all nodes on the boundary of the tree in an anti-clockwise direction -> Option A

4. Quick Check:

   Boundary traversal = print edges anti-clockwise [OK]

Hint: Boundary traversal prints edges anti-clockwise [OK]

Common Mistakes:

• Confusing boundary traversal with level order traversal
• Thinking it prints only leaf nodes
• Mixing it up with in-order traversal

2. Which of the following is the correct C function signature to perform boundary traversal on a binary tree node pointer named root?

easy

A. void boundaryTraversal(struct Node* root);

B. int boundaryTraversal(Node root);

C. void boundaryTraversal(Node root);

D. int boundaryTraversal(struct Node* root);

Solution

1. Step 1: Check parameter type for binary tree node

   Binary tree nodes are usually passed as pointers to struct Node in C.

2. Step 2: Check return type for traversal functions

   Traversal functions usually return void as they print nodes or store results externally.

3. Final Answer:

   void boundaryTraversal(struct Node* root); -> Option A

4. Quick Check:

   Pointer parameter + void return = void boundaryTraversal(struct Node* root); [OK]

Hint: Traversal functions usually take pointer and return void [OK]

Common Mistakes:

• Using struct keyword incorrectly
• Passing node by value instead of pointer
• Returning int instead of void

3. Consider the following binary tree:

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

What is the output of the boundary traversal (anti-clockwise) of this tree?

medium

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

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

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

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

Solution

1. Step 1: Identify left boundary nodes

   Left boundary excluding leaves: 1, 2

2. Step 2: Identify leaf nodes left to right

   Leaves: 4, 7, 8, 9, 10

3. Step 3: Identify right boundary nodes bottom-up excluding leaves

   Right boundary: 6, 3

4. Step 4: Combine in anti-clockwise order

   Boundary traversal: 1, 2, 4, 7, 8, 9, 10, 6, 3

5. Final Answer:

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

6. Quick Check:

   Left boundary + leaves + right boundary = [1, 2, 4, 7, 8, 9, 10, 6, 3] [OK]

Hint: Left boundary + leaves + right boundary in order [OK]

Common Mistakes:

• Including leaf nodes twice in boundary
• Wrong order of right boundary nodes
• Missing some leaf nodes

4. The following C code snippet is intended to print the boundary traversal of a binary tree. What is the error?

void printLeftBoundary(Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    if (root->left) {
        printLeftBoundary(root->left);
    } else if (root->right) {
        printLeftBoundary(root->right);
    }
}

medium

A. It does not print the root node

B. It prints leaf nodes which should be excluded in left boundary

C. It does not handle NULL root correctly

D. It prints nodes in bottom-up order instead of top-down

Solution

1. Step 1: Analyze printing condition in left boundary

   Function prints node data before recursive call, so top-down order is correct.

2. Step 2: Check if leaf nodes are excluded

   The printf is before the child checks, so leaf nodes are printed before returning.

3. Step 3: Identify error

   Leaf nodes should not be printed in left boundary function; they are printed separately in leaf traversal.

4. Final Answer:

   It prints leaf nodes which should be excluded in left boundary -> Option B

5. Quick Check:

   Left boundary excludes leaves [OK]

Hint: Exclude leaf nodes in left boundary function [OK]

Common Mistakes:

• Printing leaf nodes in left or right boundary functions
• Not checking for NULL root
• Printing nodes in wrong order

5. Given a binary tree where some nodes have only one child, how should the boundary traversal be adapted to correctly include all boundary nodes without duplicates? Choose the best approach.

hard

A. Traverse all nodes in level order and print only those with one child

B. Traverse left and right boundaries including leaves, then print all leaves

C. Print all nodes in in-order traversal and remove duplicates afterwards

D. Traverse left boundary top-down excluding leaves, then all leaves left to right, then right boundary bottom-up excluding leaves, skipping duplicates

Solution

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

   Nodes with one child may appear in left or right boundary or as leaves.

2. Step 2: Avoid duplicates by excluding leaves in boundary traversals

   Left and right boundary traversals exclude leaves to avoid duplicates; leaves are printed separately.

3. Step 3: Combine traversals carefully

   Traverse left boundary top-down excluding leaves, then leaves left to right, then right boundary bottom-up excluding leaves, skipping duplicates.

4. Final Answer:

   Traverse left boundary top-down excluding leaves, then all leaves left to right, then right boundary bottom-up excluding leaves, skipping duplicates -> Option D

5. Quick Check:

   Exclude leaves in boundaries, print leaves separately [OK]

Hint: Exclude leaves in boundaries, print leaves separately [OK]

Common Mistakes:

• Including leaves in both boundary and leaf traversals causing duplicates
• Ignoring nodes with single child in boundary
• Printing nodes in wrong order