Boundary Traversal of Binary Tree in DSA C#

Mental Model

We want to visit the outer edge nodes of a tree in a specific order: left edge top-down, leaves left to right, then right edge bottom-up.

Analogy: Imagine walking around the outside of a garden shaped like a tree, touching all the plants on the boundary without going inside.

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

Boundary order: 1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3 -> null

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6 / \ / 7 8 9 Goal: Print boundary traversal in order

Goal: Print all boundary nodes in anti-clockwise order starting from root: left boundary, leaves, right boundary

Step 1: Add root node 1 to boundary list

Boundary: 1

Why: Root is always part of boundary

Step 2: Traverse left boundary excluding leaves: add 2

Boundary: 1 -> 2

Why: Left edge nodes from top to bottom except leaves

Step 3: Add all leaf nodes from left to right: 4, 7, 8, 9

Boundary: 1 -> 2 -> 4 -> 7 -> 8 -> 9

Why: Leaves are part of boundary, collected in left-to-right order

Step 4: Traverse right boundary excluding leaves bottom-up: add 6 then 3

Boundary: 1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3

Why: Right edge nodes from bottom to top except leaves

Result:

1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3 -> null

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

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

class BoundaryTraversal {
    public static void PrintBoundary(Node root) {
        if (root == null) return;
        Console.Write(root.data + " -> "); // root always printed

        // Print left boundary excluding leaves
        PrintLeftBoundary(root.left);

        // Print all leaves
        PrintLeaves(root.left);
        PrintLeaves(root.right);

        // Print right boundary excluding leaves in reverse
        PrintRightBoundary(root.right);

        Console.WriteLine("null");
    }

    static void PrintLeftBoundary(Node node) {
        if (node == null) return;
        if (node.left != null) {
            Console.Write(node.data + " -> "); // top-down
            PrintLeftBoundary(node.left);
        } else if (node.right != null) {
            Console.Write(node.data + " -> ");
            PrintLeftBoundary(node.right);
        }
        // do nothing if leaf
    }

    static void PrintRightBoundary(Node node) {
        if (node == null) return;
        if (node.right != null) {
            PrintRightBoundary(node.right);
            Console.Write(node.data + " -> "); // bottom-up
        } else if (node.left != null) {
            PrintRightBoundary(node.left);
            Console.Write(node.data + " -> ");
        }
        // do nothing if leaf
    }

    static void PrintLeaves(Node node) {
        if (node == null) return;
        PrintLeaves(node.left);
        if (node.left == null && node.right == null) {
            Console.Write(node.data + " -> ");
        }
        PrintLeaves(node.right);
    }

    static void Main() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.left.right.left = new Node(7);
        root.left.right.right = new Node(8);
        root.right.right = new Node(6);
        root.right.right.left = new Node(9);

        PrintBoundary(root);
    }
}

Console.Write(root.data + " -> "); // root always printed

Add root node to boundary list

PrintLeftBoundary(root.left);

Traverse left boundary top-down excluding leaves

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

Add all leaf nodes from left to right

PrintRightBoundary(root.right);

Traverse right boundary bottom-up excluding leaves

Console.Write(node.data + " -> "); // top-down in PrintLeftBoundary

Add left boundary node before recursive call to go top-down

PrintRightBoundary(node.right); Console.Write(node.data + " -> "); // bottom-up in PrintRightBoundary

Recursive call first then add node to print right boundary bottom-up

if (node.left == null && node.right == null) { Console.Write(node.data + " -> "); }

Add leaf nodes only

Output

1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3 -> null

Complexity Analysis

Time: O(n) because we visit each node at most twice during the traversals

Space: O(h) where h is tree height due to recursion stack in worst case

vs Alternative: Naive approach might collect all nodes and filter boundary later, costing more time and space

Edge Cases

Empty tree

No output, function returns immediately

DSA C#

if (root == null) return;

Tree with only root node

Only root printed as boundary

DSA C#

Console.Write(root.data + " -> ");

Tree with no left subtree

Left boundary traversal skips, leaves and right boundary printed correctly

DSA C#

PrintLeftBoundary(root.left); // handles null gracefully

Tree with no right subtree

Right boundary traversal skips, left boundary and leaves printed correctly

DSA C#

PrintRightBoundary(root.right); // handles null gracefully

When to Use This Pattern

When asked to print or collect all nodes on the outer edge of a tree in order, use boundary traversal to combine left edge, leaves, and right edge.

Common Mistakes

Mistake: Including leaf nodes twice by adding them in both left/right boundary and leaves
Fix: Exclude leaves from left and right boundary traversals by checking if node is leaf before printing

Mistake: Printing right boundary top-down instead of bottom-up
Fix: Use recursion to print right boundary nodes after recursive calls to reverse order

Summary

Prints the outer boundary nodes of a binary tree in anti-clockwise order.

Use when you need to visit all edge nodes of a tree without duplicates.

The key is to separately handle left boundary, leaves, and right boundary in correct order.

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