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

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

Execution Sample

DSA C#

void BoundaryTraversal(Node root) {
  if (root == null) return;
  Console.Write(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 the order: root, left boundary, leaves, right boundary.

Execution Table

Step	Operation	Nodes in Boundary List	Pointer Changes	Visual State
1	Start at root	[1]	root points to 1	1
2	Add left boundary top-down	[1, 2, 4]	current moves down left boundary	1 -> 2 -> 4
3	Add leaves from left subtree	[1, 2, 4, 8, 9]	visited leaves 8, 9	1 -> 2 -> 4 -> 8 -> 9
4	Add leaves from right subtree	[1, 2, 4, 8, 9, 5, 10]	visited leaves 5, 10	1 -> 2 -> 4 -> 8 -> 9 -> 5 -> 10
5	Add right boundary bottom-up	[1, 2, 4, 8, 9, 5, 10, 7, 3]	current moves up right boundary	1 -> 2 -> 4 -> 8 -> 9 -> 5 -> 10 -> 7 -> 3
6	Traversal complete	[1, 2, 4, 8, 9, 5, 10, 7, 3]	no pointer changes	1 -> 2 -> 4 -> 8 -> 9 -> 5 -> 10 -> 7 -> 3

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
boundaryList	[]	[1, 2, 4]	[1, 2, 4, 8, 9]	[1, 2, 4, 8, 9, 5, 10]	[1, 2, 4, 8, 9, 5, 10, 7, 3]	[1, 2, 4, 8, 9, 5, 10, 7, 3]
current	root(1)	4 (end of left boundary)	4 (left subtree leaves)	10 (right subtree leaves)	3 (right boundary root)	3 (end)

Key Moments - 3 Insights

Why do we add the right boundary nodes in bottom-up order?

Because the right boundary must be printed from bottom to top to maintain the correct boundary order, as shown in steps 5 and 6 of the execution_table.

Why are leaves collected separately from left and right subtrees?

Leaves are collected separately to avoid duplicates and ensure all leaf nodes are included, as seen in steps 3 and 4 where leaves from left and right subtrees are added.

Why do we not add the root node again in left or right boundary traversals?

The root is added once at the start (step 1). Left and right boundary traversals start from root.left and root.right respectively to avoid duplication, as shown in the pointer changes.

Visual Quiz - 3 Questions

Look at the execution_table, what nodes are in the boundary list after step 3?

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

B [1, 2, 4]

C [1, 2, 4, 5, 10]

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

💡 Hint

Check the 'Nodes in Boundary List' column at step 3 in execution_table.

At which step does the traversal add the right boundary nodes?

A Step 2

B Step 5

C Step 4

D Step 3

💡 Hint

Look at the 'Operation' column in execution_table for when right boundary is added.

If the tree has no right subtree, how would the boundary list change after step 5?

A Right boundary nodes would be added as null

B Leaves would be added again

C Right boundary nodes would be empty, so list remains same as after step 4

D Root would be added again

💡 Hint

Refer to variable_tracker and execution_table steps for right boundary addition.

Concept Snapshot

Boundary Traversal of Binary Tree:
- Start with root node
- Traverse left boundary top-down (excluding leaves)
- Traverse all leaves left to right
- Traverse right boundary bottom-up (excluding leaves)
- Combine all for full boundary traversal
- Avoid duplicates by careful subtree traversal

Full Transcript

Boundary traversal of a binary tree collects nodes on the outer edge in a specific order: root, left boundary top-down, leaves left to right, and right boundary bottom-up. The root node is added first. Then, the left boundary is traversed from top to bottom excluding leaves. Next, all leaf nodes are collected from left and right subtrees to include all leaves. Finally, the right boundary is traversed from bottom to top excluding leaves. This order ensures the boundary nodes are printed without duplicates. The execution table shows each step adding nodes to the boundary list and pointer movements. Key moments clarify why right boundary is added bottom-up and why leaves are collected separately. The visual quiz tests understanding of boundary list contents at different steps and effects of missing subtrees.

Practice

1. What does the Boundary Traversal of a binary tree include?

easy

A. Only the root node

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

C. All nodes in level order

D. Only the leaf nodes of the tree

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.

2. Step 2: Combine these parts in order

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

3. Final Answer:

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

4. Quick Check:

   Boundary traversal = left + leaves + right [OK]

Hint: Remember: left edge, leaves, right edge in sequence [OK]

Common Mistakes:

• Including root multiple times
• Missing leaf nodes
• Reversing right boundary order

2. Which of the following C# method signatures is correct for a function that performs boundary traversal on a binary tree node root and returns a list of integers?

easy

A. public void BoundaryTraversal(int root)

B. public int BoundaryTraversal(Node root)

C. public List<int> BoundaryTraversal(Node root)

D. public List BoundaryTraversal(Node root)

Solution

1. Step 1: Check return type and parameter

   Boundary traversal returns a list of node values, so return type should be List<int> and parameter should be Node.

2. Step 2: Validate method signature syntax

   public List<int> BoundaryTraversal(Node root) matches correct syntax: public List<int> BoundaryTraversal(Node root)

3. Final Answer:

   public List<int> BoundaryTraversal(Node root) -> Option C

4. Quick Check:

   Return list<int> and input Node root [OK]

Hint: Return list of ints, input is Node root [OK]

Common Mistakes:

• Using void return type
• Wrong parameter type (int instead of Node)
• Missing generic type in List

3. Given the following binary tree:

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

What is the boundary traversal output?

medium

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

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

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

D. [1, 2, 4, 5, 7, 8, 9, 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

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

   Right boundary (excluding leaves): 3, 6

4. Step 4: Combine nodes without duplicates

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

5. Final Answer:

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

6. Quick Check:

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

Hint: Left edge + leaves + right edge reversed [OK]

Common Mistakes:

• Including leaf nodes twice
• Missing right boundary node 3
• Wrong order of leaves

4. Consider this C# code snippet for boundary traversal:

void PrintLeftBoundary(Node node) {
  if (node == null) return;
  Console.Write(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 skips left boundary nodes

B. It does not print the root node

C. It causes infinite recursion on leaf nodes

D. It prints leaf nodes which should be excluded

Solution

1. Step 1: Analyze leaf node printing

   The code prints node data before recursive call even if node is leaf, so leaf nodes get printed here.

2. Step 2: Understand boundary traversal rules

   Left boundary function should exclude leaf nodes to avoid duplicates in leaf printing step.

3. Final Answer:

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

4. Quick Check:

   Left boundary excludes leaves [OK]

Hint: Exclude leaves in left boundary print [OK]

Common Mistakes:

• Printing leaves in left boundary
• Not checking for null nodes
• Confusing left and right child checks

5. You want to perform boundary traversal on a binary tree but avoid printing duplicate nodes when the tree has only one node or skewed structure. Which approach is best?

hard

A. Print root, then left boundary excluding leaves, then leaves excluding root, then right boundary excluding leaves and root

B. Print all nodes in preorder traversal

C. Print leaves only once and ignore boundaries

D. Print left boundary including leaves, then right boundary including leaves

Solution

1. Step 1: Avoid duplicates by excluding leaves in boundaries

   Exclude leaves from left and right boundary to prevent duplicates with leaf traversal.

2. Step 2: Handle root separately

   Print root once at start, exclude it from right boundary to avoid repetition.

3. Step 3: Combine all parts carefully

   Print root, left boundary (no leaves), leaves (excluding root), right boundary (no leaves or root) for correct order and no duplicates.

4. Final Answer:

   Print root, then left boundary excluding leaves, then leaves excluding root, then right boundary excluding leaves and root -> Option A

5. Quick Check:

   Exclude duplicates by careful boundary and leaf separation [OK]

Hint: Exclude leaves in boundaries, print root once [OK]

Common Mistakes:

• Printing root multiple times
• Including leaves in boundaries causing duplicates
• Ignoring skewed tree edge cases