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 (top-down)

↓

Traverse leaves (left to right)

↓

Traverse right boundary (bottom-up)

↓

Combine all parts for boundary traversal

Start from root, add left boundary nodes 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;
  cout << root->data << " ";
  printLeftBoundary(root->left);
  printLeaves(root->left);
  printLeaves(root->right);
  printRightBoundary(root->right);
}

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

Execution Table

Step	Operation	Nodes Visited	Pointer Changes	Visual State
1	Start at root	Root(20)	root -> 20	20
2	Add root to boundary	20	boundary = [20]	20
3	Traverse left boundary top-down	15, 10	current moves left	20 -> 15 -> 10
4	Traverse leaves left to right	8, 12, 25, 30	leaf nodes collected	20 -> 15 -> 10 -> 8 -> 12 -> 25 -> 30
5	Traverse right boundary bottom-up	35, 40	current moves right	20 -> 15 -> 10 -> 8 -> 12 -> 25 -> 30 -> 40 -> 35
6	Combine all parts	All boundary nodes	boundary list finalized	20 -> 15 -> 10 -> 8 -> 12 -> 25 -> 30 -> 40 -> 35
7	End	Traversal complete	No changes	Final boundary traversal output

💡 All boundary nodes visited and printed in anti-clockwise order

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
root	Node(20)	Node(20)	Node(20)	Node(20)	Node(20)	Node(20)
boundary	[]	[20]	[20, 15, 10]	[20, 15, 10, 8, 12, 25, 30]	[20, 15, 10, 8, 12, 25, 30, 40, 35]	[20, 15, 10, 8, 12, 25, 30, 40, 35]
current	null	null	Node(10)	null	Node(40)	null

Key Moments - 3 Insights

Why do we traverse the right boundary bottom-up instead of top-down?

Because the boundary traversal is anti-clockwise, the right boundary nodes must be added after leaves in reverse order to maintain correct sequence, as shown in step 5 of execution_table.

Why do we separately traverse leaves after left boundary?

Leaves can be anywhere in the tree, not just on boundaries. Traversing leaves separately ensures all leaf nodes are included, as seen in step 4 where leaves 8, 12, 25, 30 are added.

What if the root has no left or right child?

Then left or right boundary traversal skips, and only root and leaves (which may be root itself) are printed. The code handles this by checking null pointers, as in step 3 and 5.

Visual Quiz - 3 Questions

Look at the execution_table, what nodes are added during step 3 (left boundary traversal)?

A 15, 10

B 20, 15, 10

C 8, 12

D 40, 35

💡 Hint

Check the 'Nodes Visited' column for step 3 in execution_table

At which step does the traversal add leaf nodes to the boundary?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for 'Traverse leaves left to right' in the Operation column

If the tree had no right child, how would the boundary list change after step 5?

A Leaves would be skipped

B Right boundary nodes would be empty, so boundary list ends after leaves

C Right boundary nodes would be same as left boundary

D Root would be added again

💡 Hint

Refer to variable_tracker and key_moments about handling null right child

Concept Snapshot

Boundary Traversal of Binary Tree:
- Start at root, add root to boundary
- Traverse left boundary top-down (excluding leaves)
- Traverse all leaves left to right
- Traverse right boundary bottom-up (excluding leaves)
- Combine all for anti-clockwise boundary
- Handles null children gracefully

Full Transcript

Boundary traversal of a binary tree prints nodes on the boundary in anti-clockwise order. It starts by adding the root node. Then it traverses the left boundary from top to bottom, excluding leaf nodes. Next, it collects all leaf nodes from left to right. Finally, it traverses the right boundary from bottom to top, excluding leaf nodes. These parts are combined to form the full boundary traversal. The traversal handles cases where left or right children are missing by skipping those parts. The execution table shows each step with nodes visited and the visual state of the boundary list. Key moments clarify why right boundary is bottom-up and why leaves are traversed separately. The visual quiz tests understanding of these steps and edge cases.