Boundary Traversal of Binary Tree in DSA Java - Execution Trace

Concept Flow - Boundary Traversal of Binary Tree

Start at root

↓

Add root to boundary

↓

Traverse left boundary (top-down)

↓

Traverse leaf nodes (left to right)

↓

Traverse right boundary (bottom-up)

↓

Combine all parts for full boundary

↓

End

The traversal collects nodes from the root, left boundary, leaves, and right boundary in order to form the full boundary of the tree.

Execution Sample

DSA Java

void boundaryTraversal(Node root) {
  if (root == null) return;
  System.out.print(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 anti-clockwise order.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Visual State
1	Start at root	1	root points to Node(1)	1
2	Add root to boundary	1	boundary = [1]	1
3	Traverse left boundary top-down	2	current moves from 2 to 4	1 -> 2 -> 4
4	Traverse left boundary top-down	4	current moves from 4 to 7	1 -> 2 -> 4 -> 7
5	Traverse left boundary top-down	7	7 is leaf, stop left boundary	1 -> 2 -> 4 -> 7
6	Traverse leaf nodes left subtree	7	leaf added	1 -> 2 -> 4 -> 7
7	Traverse leaf nodes left subtree	8	leaf added	1 -> 2 -> 4 -> 7 -> 8
8	Traverse leaf nodes right subtree	5	leaf added	1 -> 2 -> 4 -> 7 -> 8 -> 5
9	Traverse leaf nodes right subtree	6	leaf added	1 -> 2 -> 4 -> 7 -> 8 -> 5 -> 6
10	Traverse right boundary bottom-up	3	current moves from 3 to 9	1 -> 2 -> 4 -> 7 -> 8 -> 5 -> 6 -> 9 -> 3
11	Traverse right boundary bottom-up	9	9 is leaf, stop right boundary	1 -> 2 -> 4 -> 7 -> 8 -> 5 -> 6 -> 9 -> 3
12	Combine all parts	N/A	boundary = [1,2,4,7,8,5,6,9,3]	1 -> 2 -> 4 -> 7 -> 8 -> 5 -> 6 -> 9 -> 3
13	End	N/A	Traversal complete	Final boundary traversal output

💡 All boundary nodes visited; traversal complete.

Variable Tracker

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

Key Moments - 3 Insights

Why do we stop adding nodes to the left boundary when we reach a leaf node?

Because leaf nodes are handled separately in the leaf traversal step to avoid duplicates. See execution_table rows 5 and 6 where traversal stops at leaf 7.

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

To maintain anti-clockwise order, right boundary nodes are added after leaves in reverse order. See execution_table rows 10 and 11 where right boundary nodes 3 and 9 are added last.

How do we avoid adding leaf nodes twice?

Leaf nodes are only added during the leaf traversal step, not during left or right boundary traversals. This is shown in execution_table rows 6-9 where leaves 7,8,5,6 are added.

Visual Quiz - 3 Questions

Look at the execution_table, what is the boundary list after step 7?

A [1, 2, 4, 7, 8]

B [1, 2, 4]

C [1, 2, 4, 7]

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

💡 Hint

Check the 'boundary list' variable in variable_tracker after step 7.

At which step does the traversal add the first leaf node?

A Step 8

B Step 5

C Step 6

D Step 10

💡 Hint

Look at execution_table rows where leaf nodes are added during leaf traversal.

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

A It would be empty

B It would be missing right boundary nodes

C It would include right boundary nodes anyway

D It would only have leaves

💡 Hint

Right boundary traversal depends on right subtree presence, see execution_table steps 10-11.

Concept Snapshot

Boundary Traversal of Binary Tree:
- Start at root, add root
- Traverse left boundary top-down (exclude leaves)
- Traverse all leaf nodes left to right
- Traverse right boundary bottom-up (exclude leaves)
- Combine all for full boundary in anti-clockwise order

Full Transcript

Boundary traversal collects nodes on the edges of a binary tree 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. This order ensures no duplicates and covers the entire boundary. The traversal stops when all boundary nodes are visited. The final output is the combined list of these nodes.

Practice

1. What is the correct order of nodes visited in a boundary traversal of a binary tree?

easy

A. Root, leaves (left to right), left boundary (top-down), right boundary (bottom-up)

B. Leaves (left to right), root, left boundary (top-down), right boundary (bottom-up)

C. Root, left boundary (top-down), leaves (left to right), right boundary (bottom-up)

D. Left boundary (top-down), root, right boundary (bottom-up), leaves (left to right)

Solution

1. Step 1: Understand boundary traversal parts

   Boundary traversal visits root, then left boundary top-down, then leaves left to right, then right boundary bottom-up.

2. Step 2: Arrange traversal order

   Root is first, left boundary next, leaves after that, and right boundary last in reverse order.

3. Final Answer:

   Root, left boundary (top-down), leaves (left to right), right boundary (bottom-up) -> Option C

4. Quick Check:

   Boundary traversal order = Root + Left + Leaves + Right [OK]

Hint: Remember: Root, Left boundary, Leaves, Right boundary [OK]

Common Mistakes:

• Mixing order of leaves and boundaries
• Visiting right boundary top-down instead of bottom-up
• Skipping root node

2. Which of the following Java method signatures is correct for a function performing boundary traversal on a binary tree node?

easy

A. public void boundaryTraversal() Node root

B. void boundaryTraversal(Node root) public

C. public boundaryTraversal(Node root) void

D. public void boundaryTraversal(Node root)

Solution

1. Step 1: Recall Java method syntax

   Java methods start with access modifier, then return type, then method name and parameters.

2. Step 2: Match correct syntax

   public void boundaryTraversal(Node root) matches: public void boundaryTraversal(Node root). Others have wrong order or missing parts.

3. Final Answer:

   public void boundaryTraversal(Node root) -> Option D

4. Quick Check:

   Access modifier + return type + method name + parameters [OK]

Hint: Java method = access modifier + return type + name + params [OK]

Common Mistakes:

• Placing return type after method name
• Missing access modifier
• Incorrect parameter placement

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

        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 boundary nodes

   Root: 1; Left boundary top-down: 2 (excluding leaf 4); Leaves left to right: 4,7,8,9; Right boundary bottom-up: 6,3 (excluding leaves).

2. Step 2: Combine nodes without duplicates

   Boundary traversal: 1 (root), 2 (left boundary), 4,7,8,9 (leaves), 6,3 (right boundary).

3. Final Answer:

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

4. Quick Check:

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

Hint: Leaves included once; right boundary reversed; avoid duplicates [OK]

Common Mistakes:

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

4. Consider this Java method snippet for boundary traversal:

void printLeftBoundary(Node node) {
  if (node == null) return;
  System.out.print(node.data + " ");
  if (node.left != null) {
    printLeftBoundary(node.left);
  } else if (node.right != null) {
    printLeftBoundary(node.right);
  }
}

What is the bug in this code?

medium

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

B. It does not print the root node

C. It causes infinite recursion on leaf nodes

D. It prints right boundary nodes instead of left

Solution

1. Step 1: Analyze leaf node printing

   The code prints node data before checking for children, thus printing leaf nodes as well.

2. Step 2: Identify leaf node exclusion missing

   Leaf nodes should not be printed in left boundary function, but this code prints them unconditionally after null check.

3. Final Answer:

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

4. Quick Check:

   Left boundary excludes leaves, code prints them [OK]

Hint: Exclude leaf nodes in boundary functions to avoid duplicates [OK]

Common Mistakes:

• Not checking if node is leaf before printing
• Confusing left and right boundary logic
• Missing base case for null nodes

5. You have a binary tree where some nodes have only right children, and leaves are only on the rightmost path. How should you modify the boundary traversal algorithm to correctly print the boundary without duplicates?

hard

A. Skip printing left boundary if no left child; print leaves only once; print right boundary bottom-up excluding leaves

B. Print all nodes in preorder to cover all boundaries and leaves

C. Print left boundary top-down including leaves; skip right boundary

D. Print leaves first, then left and right boundaries in any order

Solution

1. Step 1: Understand tree structure

   Since leaves are only on rightmost path and some nodes have only right children, left boundary may be missing or partial.

2. Step 2: Modify traversal rules

   Skip left boundary if no left child; print leaves once; print right boundary bottom-up excluding leaves to avoid duplicates.

3. Step 3: Combine for correct boundary

   This ensures no duplicates and correct order for such skewed trees.

4. Final Answer:

   Skip printing left boundary if no left child; print leaves only once; print right boundary bottom-up excluding leaves -> Option A

5. Quick Check:

   Handle missing left boundary and leaf duplicates carefully [OK]

Hint: Skip missing boundaries; print leaves once; reverse right boundary [OK]

Common Mistakes:

• Printing leaves multiple times
• Ignoring missing left boundary
• Printing right boundary top-down causing wrong order