Boundary Traversal of Binary Tree in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Boundary Traversal on a Simple Binary Tree

What is the output of the boundary traversal for the following binary tree?

Tree structure:
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8

DSA C#

class Node {
    public int data;
    public Node left, right;
    public Node(int d) { data = d; left = right = null; }
}

// Boundary traversal function returns list of node data in boundary order
List<int> BoundaryTraversal(Node root) {
    List<int> res = new List<int>();
    if (root == null) return res;
    res.Add(root.data);

    void AddLeftBoundary(Node node) {
        Node cur = node;
        while (cur != null) {
            if (cur.left != null || cur.right != null) res.Add(cur.data);
            if (cur.left != null) cur = cur.left;
            else cur = cur.right;
        }
    }

    void AddLeaves(Node node) {
        if (node == null) return;
        AddLeaves(node.left);
        if (node.left == null && node.right == null) res.Add(node.data);
        AddLeaves(node.right);
    }

    void AddRightBoundary(Node node) {
        Stack<int> s = new Stack<int>();
        Node cur = node;
        while (cur != null) {
            if (cur.left != null || cur.right != null) s.Push(cur.data);
            if (cur.right != null) cur = cur.right;
            else cur = cur.left;
        }
        while (s.Count > 0) res.Add(s.Pop());
    }

    AddLeftBoundary(root.left);
    AddLeaves(root.left);
    AddLeaves(root.right);
    AddRightBoundary(root.right);

    return res;
}

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

B [1, 2, 4, 5, 7, 8, 6, 3]

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

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

💡 Hint

Remember boundary traversal includes left boundary (excluding leaves), all leaves, and right boundary (excluding leaves) in reverse.

The boundary traversal starts at root (1), then left boundary excluding leaves (2), then leaves in left to right order (4,7,8,6), then right boundary excluding leaves in reverse (3). Node 5 is not on boundary as it is internal leaf's parent.

❓ Predict Output

intermediate

Boundary Traversal Output for Single Node Tree

What is the output of the boundary traversal for a binary tree with only one node (value 10)?

DSA C#

class Node {
    public int data;
    public Node left, right;
    public Node(int d) { data = d; left = right = null; }
}

List<int> BoundaryTraversal(Node root) {
    List<int> res = new List<int>();
    if (root == null) return res;
    res.Add(root.data);

    void AddLeftBoundary(Node node) {
        Node cur = node;
        while (cur != null) {
            if (cur.left != null || cur.right != null) res.Add(cur.data);
            if (cur.left != null) cur = cur.left;
            else cur = cur.right;
        }
    }

    void AddLeaves(Node node) {
        if (node == null) return;
        AddLeaves(node.left);
        if (node.left == null && node.right == null) res.Add(node.data);
        AddLeaves(node.right);
    }

    void AddRightBoundary(Node node) {
        Stack<int> s = new Stack<int>();
        Node cur = node;
        while (cur != null) {
            if (cur.left != null || cur.right != null) s.Push(cur.data);
            if (cur.right != null) cur = cur.right;
            else cur = cur.left;
        }
        while (s.Count > 0) res.Add(s.Pop());
    }

    AddLeftBoundary(root.left);
    AddLeaves(root.left);
    AddLeaves(root.right);
    AddRightBoundary(root.right);

    return res;
}

A [null]

B []

C [10, 10]

D [10]

💡 Hint

A single node tree's boundary traversal is just the root node.

Since the tree has only one node, the boundary traversal is just that node's value.

🔧 Debug

advanced

Identify the Logical Error in Boundary Traversal Code

Given the following code snippet for boundary traversal, what is the logical error that causes incorrect output?

DSA C#

void AddLeftBoundary(Node node) {
    Node cur = node;
    while (cur != null) {
        res.Add(cur.data);
        if (cur.left != null) cur = cur.left;
        else cur = cur.right;
    }
}

void AddRightBoundary(Node node) {
    Stack<int> s = new Stack<int>();
    Node cur = node;
    while (cur != null) {
        s.Push(cur.data);
        if (cur.right != null) cur = cur.right;
        else cur = cur.left;
    }
    while (s.Count > 0) res.Add(s.Pop());
}

A Left boundary traversal misses nodes with only right child.

B Leaves are included in left and right boundary causing duplicates in output.

C Right boundary traversal adds nodes in wrong order causing reversed output.

D Stack used in right boundary traversal causes runtime error.

💡 Hint

Check if leaves are excluded from left and right boundary to avoid duplicates.

The code adds all nodes in left and right boundary including leaves, which are also added separately in leaves traversal, causing duplicates.

🧠 Conceptual

advanced

Understanding Boundary Traversal Components

Which of the following correctly describes the three main parts of a boundary traversal of a binary tree?

A Root node, all leaf nodes, right boundary including leaves in normal order.

B All nodes in left subtree, all leaf nodes, all nodes in right subtree.

C Left boundary excluding leaves, all leaf nodes, right boundary excluding leaves in reverse order.

D Left boundary including leaves, all nodes in the tree, right boundary excluding leaves.

💡 Hint

Boundary traversal excludes leaves from left and right boundaries to avoid duplicates.

Boundary traversal includes left boundary excluding leaves, all leaves, and right boundary excluding leaves in reverse order.

🚀 Application

expert

Number of Nodes in Boundary Traversal Output

Given a perfect binary tree of height 3 (levels 0 to 3), how many nodes will be in the boundary traversal output?

A 9

B 8

C 7

D 10

💡 Hint

Count nodes on left boundary excluding leaves, leaves, and right boundary excluding leaves carefully.

A perfect binary tree of height 3 has 15 nodes. Left boundary excluding leaves has 2 nodes, leaves are 8 nodes, right boundary excluding leaves has 2 nodes, plus root counted once. Total = 1 (root) + 2 + 8 + 2 = 13 but root counted once, so total nodes in boundary traversal is 9 (root + left boundary excluding leaves + leaves + right boundary excluding leaves without duplicates).

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