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.

Practice

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

easy

A. Left boundary, leaves, and right boundary nodes in order

B. Only leaf nodes from left to right

C. All nodes in level order

D. Only root and leaf nodes

Solution

1. Step 1: Understand boundary traversal components

   Boundary traversal includes the left boundary (excluding leaves), all leaf nodes, and the right boundary (excluding leaves) in reverse order.

2. Step 2: Combine all parts in order

   Traverse left boundary top-down, then leaves left to right, then right boundary bottom-up to get the full boundary traversal.

3. Final Answer:

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

4. Quick Check:

   Boundary traversal = Left boundary + Leaves + Right boundary [OK]

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

Common Mistakes:

• Including leaf nodes twice in left or right boundary
• Ignoring right boundary order (should be bottom-up)
• Confusing boundary traversal with level order

2. Which of the following C++ function signatures is correct for printing the left boundary of a binary tree?

easy

A. void printLeftBoundary(Node* root);

B. int printLeftBoundary(Node root);

C. void printLeftBoundary(Node root);

D. int printLeftBoundary(Node* root);

Solution

1. Step 1: Identify correct parameter type for tree node

   Binary tree nodes are passed as pointers (Node*), not by value (Node), to avoid copying the entire subtree.

2. Step 2: Check return type for printing function

   Printing functions usually return void as they output directly and do not return a value.

3. Final Answer:

   void printLeftBoundary(Node* root); -> Option A

4. Quick Check:

   Pointer parameter + void return = correct signature [OK]

Hint: Use pointer parameter and void return for print functions [OK]

Common Mistakes:

• Passing node by value causing unnecessary copies
• Using int return type for printing functions
• Missing pointer symbol (*) in parameter

3. Given the binary tree below, what is the boundary traversal output?

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

medium

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

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

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

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

Solution

1. Step 1: Identify left boundary nodes excluding leaves

   Left boundary: 1, 2 (4 is leaf, so excluded here)

2. Step 2: Collect all leaf nodes left to right

   Leaves: 4, 7, 8, 9

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

   Right boundary: 6, 3

4. Step 4: Combine all parts

   Boundary traversal = [1, 2] + [4, 7, 8, 9] + [6, 3] = [1, 2, 4, 7, 8, 9, 6, 3]

5. Final Answer:

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

6. Quick Check:

   Left boundary + leaves + right boundary = [1, 2, 4, 7, 8, 9, 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 code snippet is intended to print the right boundary of a binary tree. What is the error?

void printRightBoundary(Node* root) {
    if (!root) return;
    if (root->right) {
        printRightBoundary(root->right);
    } else if (root->left) {
        printRightBoundary(root->left);
    }
    std::cout << root->data << " ";
}

medium

A. It misses printing the root node

B. It does not print nodes in bottom-up order

C. It prints leaf nodes which should be excluded

D. It causes infinite recursion

Solution

1. Step 1: Analyze printing condition in recursion

   The function prints every node after recursive calls, including leaf nodes which should be excluded from right boundary printing.

2. Step 2: Identify missing leaf node check

   There is no check to skip printing leaf nodes, so leaf nodes get printed incorrectly as part of right boundary.

3. Final Answer:

   It prints leaf nodes which should be excluded -> Option C

4. Quick Check:

   Leaf nodes must be excluded from right boundary [OK]

Hint: Skip printing leaf nodes in boundary functions [OK]

Common Mistakes:

• Printing leaf nodes in boundary traversal
• Not checking for null nodes before recursion
• Confusing order of printing nodes

5. You want to perform boundary traversal on a binary tree that may have only one node or be skewed (all left or all right). Which approach correctly handles these edge cases?

hard

A. Print only leaf nodes as boundary in skewed trees

B. Print all nodes in level order to cover all cases

C. Print left boundary including leaves, then right boundary including leaves, ignoring root

D. Print root, then left boundary excluding leaves, then leaves, then right boundary excluding leaves, skipping duplicates

Solution

1. Step 1: Understand edge cases in boundary traversal

   Single node tree or skewed trees may cause duplicates if leaves are included in boundaries without checks.

2. Step 2: Use approach that prints root, left boundary excluding leaves, leaves, right boundary excluding leaves, and skip duplicates

   This ensures no node is printed twice and all edge cases are handled correctly.

3. Final Answer:

   Print root, then left boundary excluding leaves, then leaves, then right boundary excluding leaves, skipping duplicates -> Option D

4. Quick Check:

   Exclude leaves in boundaries + skip duplicates [OK]

Hint: Exclude leaves in boundaries and skip duplicates [OK]

Common Mistakes:

• Printing leaves twice in skewed trees
• Ignoring root node in traversal
• Using level order which is not boundary traversal