Boundary Traversal of Binary Tree in DSA C# - Build from Scratch

Boundary Traversal of Binary Tree

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to visit all the family members who are on the outer edge of the tree, starting from the oldest ancestor on the left side, then all the youngest descendants at the bottom, and finally the oldest ancestors on the right side, without repeating anyone.

🎯 Goal: Build a program that performs a boundary traversal of a binary tree. This means printing the nodes on the left boundary (top to bottom), then all the leaf nodes (left to right), and finally the nodes on the right boundary (bottom to top), forming a complete outline of the tree.

📋 What You'll Learn

Create a binary tree with the exact structure given

Add helper variables or methods to identify leaf nodes

Implement the boundary traversal logic using separate methods for left boundary, leaves, and right boundary

Print the boundary traversal nodes in the correct order

💡 Why This Matters

🌍 Real World

Boundary traversal helps in graphical rendering of tree structures, outlining shapes, and in applications like network topology visualization where edge nodes are important.

💼 Career

Understanding tree traversals and boundary traversal is useful for software engineers working with hierarchical data, UI trees, and algorithms involving tree data structures.

1

Create the Binary Tree Structure

Create a class called Node with an int data field and two Node references called left and right. Then create the exact binary tree shown below by creating Node objects and linking them:

Root node with data 20
Left child of root: 8
Right child of root: 22
Left child of node 8: 4
Right child of node 8: 12
Left child of node 12: 10
Right child of node 12: 14
Right child of node 22: 25

DSA C#

// Define Node class and create the binary tree as described
// Your code here

Hint

Start by defining the Node class with data and two child references. Then build the tree by creating nodes and linking them exactly as described.

2

Add Helper Method to Check Leaf Nodes

Inside the BinaryTree class, add a method called IsLeaf that takes a Node parameter called node and returns true if both node.left and node.right are null, otherwise returns false.

DSA C#

public class Node
{
    public int data;
    public Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

public class BinaryTree
{
    public Node root;

    public BinaryTree()
    {
        root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(4);
        root.left.right = new Node(12);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        root.right.right = new Node(25);
    }

    // Add IsLeaf method below
    // Your code here
}

Hint

This method helps to identify if a node is a leaf by checking if it has no children.

3

Implement Boundary Traversal Logic

Inside the BinaryTree class, add three methods:
1. PrintLeftBoundary(Node node): Print all nodes on the left boundary except leaf nodes, top to bottom.
2. PrintLeaves(Node node): Print all leaf nodes from left to right.
3. PrintRightBoundary(Node node): Print all nodes on the right boundary except leaf nodes, bottom to top.
Use Console.Write(node.data + " ") to print nodes.
Then add a method PrintBoundary() that prints the root node data, calls PrintLeftBoundary with root.left, PrintLeaves with root.left and root.right, and finally PrintRightBoundary with root.right.

DSA C#

public class Node
{
    public int data;
    public Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

public class BinaryTree
{
    public Node root;

    public BinaryTree()
    {
        root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(4);
        root.left.right = new Node(12);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        root.right.right = new Node(25);
    }

    public bool IsLeaf(Node node)
    {
        return node.left == null && node.right == null;
    }

    // Add PrintLeftBoundary, PrintLeaves, PrintRightBoundary, and PrintBoundary methods below
    // Your code here
}

Hint

Use recursion to print left boundary top-down, leaves left-to-right, and right boundary bottom-up. Print the root first, then left boundary, leaves, and right boundary.

4

Print the Boundary Traversal Result

In the Main method, create an instance of BinaryTree called tree. Then call tree.PrintBoundary() to print the boundary traversal of the tree.

DSA C#

using System;

public class Node
{
    public int data;
    public Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

public class BinaryTree
{
    public Node root;

    public BinaryTree()
    {
        root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(4);
        root.left.right = new Node(12);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        root.right.right = new Node(25);
    }

    public bool IsLeaf(Node node)
    {
        return node.left == null && node.right == null;
    }

    public void PrintLeftBoundary(Node node)
    {
        if (node == null) return;
        if (!IsLeaf(node))
        {
            Console.Write(node.data + " ");
        }
        if (node.left != null)
        {
            PrintLeftBoundary(node.left);
        }
        else if (node.right != null)
        {
            PrintLeftBoundary(node.right);
        }
    }

    public void PrintLeaves(Node node)
    {
        if (node == null) return;
        PrintLeaves(node.left);
        if (IsLeaf(node))
        {
            Console.Write(node.data + " ");
        }
        PrintLeaves(node.right);
    }

    public void PrintRightBoundary(Node node)
    {
        if (node == null) return;
        if (node.right != null)
        {
            PrintRightBoundary(node.right);
        }
        else if (node.left != null)
        {
            PrintRightBoundary(node.left);
        }
        if (!IsLeaf(node))
        {
            Console.Write(node.data + " ");
        }
    }

    public void PrintBoundary()
    {
        if (root == null) return;
        Console.Write(root.data + " ");

        PrintLeftBoundary(root.left);

        PrintLeaves(root.left);
        PrintLeaves(root.right);

        PrintRightBoundary(root.right);
    }
}

class Program
{
    static void Main()
    {
        // Create BinaryTree instance and print boundary
        // Your code here
    }
}

Hint

Create the tree instance and call PrintBoundary() to see the boundary traversal printed.

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