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 edge of a garden: first along the left fence from top to bottom, then along the flowers at the bottom, and finally up the right fence back to the start.

       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 of this tree.

Goal: Print nodes on the boundary in order: left boundary top-down, leaves left to right, right boundary bottom-up.

Step 1: Add root node 1 to boundary list

Boundary: 1

Why: Root is always part of the boundary

Step 2: Traverse left boundary excluding leaves: add 2

Boundary: 1 -> 2

Why: Left boundary nodes are added top-down excluding leaves to avoid duplicates

Step 3: Add leaf nodes from left subtree: 4, 7 and 8

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

Why: Leaves are added left to right to include all bottom nodes

Step 4: Add leaf nodes from right subtree: 9

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

Why: Leaves on right subtree are added after left subtree leaves

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

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

Why: Right boundary nodes are added bottom-up excluding leaves to avoid duplicates

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define binary tree node
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Check if node is leaf
int isLeaf(Node* node) {
    return (node->left == NULL && node->right == NULL);
}

// Print left boundary excluding leaves
void printLeftBoundary(Node* node) {
    if (node == NULL) return;
    if (!isLeaf(node)) {
        printf("%d -> ", node->data); // print before going down
    }
    if (node->left) {
        printLeftBoundary(node->left); // go left if possible
    } else if (node->right) {
        printLeftBoundary(node->right); // else go right
    }
}

// Print leaf nodes in left to right order
void printLeaves(Node* node) {
    if (node == NULL) return;
    printLeaves(node->left); // left subtree leaves first
    if (isLeaf(node)) {
        printf("%d -> ", node->data); // print leaf
    }
    printLeaves(node->right); // right subtree leaves
}

// Print right boundary excluding leaves bottom-up
void printRightBoundary(Node* node) {
    if (node == NULL) return;
    if (node->right) {
        printRightBoundary(node->right); // go right if possible
    } else if (node->left) {
        printRightBoundary(node->left); // else go left
    }
    if (!isLeaf(node)) {
        printf("%d -> ", node->data); // print after recursion to get bottom-up
    }
}

// Boundary traversal function
void boundaryTraversal(Node* root) {
    if (root == NULL) return;
    printf("%d -> ", root->data); // root always printed

    // Left boundary excluding root and leaves
    printLeftBoundary(root->left);

    // All leaf nodes
    printLeaves(root->left);
    printLeaves(root->right);

    // Right boundary excluding root and leaves
    printRightBoundary(root->right);

    printf("null\n");
}

// Driver code
int main() {
    /* Construct the following tree
           1
          / \
         2   3
        / \   \
       4   5   6
          / \   \
         7   8   9
    */
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->left->right->left = newNode(7);
    root->left->right->right = newNode(8);
    root->right->right = newNode(6);
    root->right->right->right = newNode(9);

    boundaryTraversal(root);
    return 0;
}

printf("%d -> ", root->data);

Print root node as start of boundary

if (!isLeaf(node)) { printf("%d -> ", node->data); }

Print left boundary nodes excluding leaves before recursion

printLeftBoundary(node->left); else printLeftBoundary(node->right);

Traverse left boundary top-down preferring left child

if (isLeaf(node)) { printf("%d -> ", node->data); }

Print leaf nodes during in-order traversal

printLeaves(root->left); printLeaves(root->right);

Traverse all leaves left to right

printRightBoundary(node->right); else printRightBoundary(node->left);

Traverse right boundary bottom-up preferring right child

if (!isLeaf(node)) { printf("%d -> ", node->data); }

Print right boundary nodes after recursion for bottom-up order

Output

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

Complexity Analysis

Time: O(n) because left and right subtrees are traversed once each to collect leaves, plus O(h) for boundary paths

Space: O(h) where h is tree height due to recursion stack during traversal

vs Alternative: Compared to naive approach that might check all nodes multiple times, this method efficiently visits each node once with clear separation of boundary parts

Edge Cases

Empty tree (root is NULL)

No output, function returns immediately

DSA C

if (root == NULL) return;

Tree with only root node

Only root node is printed as boundary

DSA C

printf("%d -> ", root->data);

Tree with only left subtree

Left boundary and leaves printed correctly without right boundary

DSA C

printRightBoundary(root->right);

Tree with only right subtree

Right boundary and leaves printed correctly without left boundary

DSA C

printLeftBoundary(root->left);

When to Use This Pattern

When a problem asks for printing or collecting nodes on the outer edge of a binary tree in a specific order, use boundary traversal to separate left boundary, leaves, and right boundary for clear and efficient output.

Common Mistakes

Mistake: Including leaf nodes twice by printing them in both boundary and leaf traversal
Fix: Exclude leaf nodes from left and right boundary printing functions

Mistake: Printing right boundary top-down instead of bottom-up
Fix: Print right boundary nodes after recursive calls to achieve bottom-up order

Mistake: Not handling cases where left or right child is NULL in boundary traversal
Fix: Check for NULL children and traverse the other child if one is missing

Summary

Prints the outer boundary nodes of a binary tree in a specific order: left boundary, leaves, then right boundary.

Use when you need to display or process the perimeter nodes of a tree distinctly from inner nodes.

The key insight is to separate the traversal into three parts and carefully avoid duplicates by excluding leaves from boundary traversals.

Practice

1. What is the main purpose of the Boundary Traversal of Binary Tree?

easy

A. To print all nodes on the boundary of the tree in an anti-clockwise direction

B. To print all nodes in level order

C. To print all leaf nodes only

D. To print nodes in in-order traversal

Solution

1. Step 1: Understand boundary traversal definition

   Boundary traversal prints nodes on the edges of the tree: left boundary, leaves, and right boundary.

2. Step 2: Compare with other traversals

   Level order prints all nodes level-wise, leaf traversal prints only leaves, in-order prints nodes in left-root-right order.

3. Final Answer:

   To print all nodes on the boundary of the tree in an anti-clockwise direction -> Option A

4. Quick Check:

   Boundary traversal = print edges anti-clockwise [OK]

Hint: Boundary traversal prints edges anti-clockwise [OK]

Common Mistakes:

• Confusing boundary traversal with level order traversal
• Thinking it prints only leaf nodes
• Mixing it up with in-order traversal

2. Which of the following is the correct C function signature to perform boundary traversal on a binary tree node pointer named root?

easy

A. void boundaryTraversal(struct Node* root);

B. int boundaryTraversal(Node root);

C. void boundaryTraversal(Node root);

D. int boundaryTraversal(struct Node* root);

Solution

1. Step 1: Check parameter type for binary tree node

   Binary tree nodes are usually passed as pointers to struct Node in C.

2. Step 2: Check return type for traversal functions

   Traversal functions usually return void as they print nodes or store results externally.

3. Final Answer:

   void boundaryTraversal(struct Node* root); -> Option A

4. Quick Check:

   Pointer parameter + void return = void boundaryTraversal(struct Node* root); [OK]

Hint: Traversal functions usually take pointer and return void [OK]

Common Mistakes:

• Using struct keyword incorrectly
• Passing node by value instead of pointer
• Returning int instead of void

3. Consider the following binary tree:

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

What is the output of the boundary traversal (anti-clockwise) of this tree?

medium

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

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

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

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

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

   Right boundary: 6, 3

4. Step 4: Combine in anti-clockwise order

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

5. Final Answer:

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

6. Quick Check:

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

Hint: Left boundary + leaves + right boundary in order [OK]

Common Mistakes:

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

4. The following C code snippet is intended to print the boundary traversal of a binary tree. What is the error?

void printLeftBoundary(Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    if (root->left) {
        printLeftBoundary(root->left);
    } else if (root->right) {
        printLeftBoundary(root->right);
    }
}

medium

A. It does not print the root node

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

C. It does not handle NULL root correctly

D. It prints nodes in bottom-up order instead of top-down

Solution

1. Step 1: Analyze printing condition in left boundary

   Function prints node data before recursive call, so top-down order is correct.

2. Step 2: Check if leaf nodes are excluded

   The printf is before the child checks, so leaf nodes are printed before returning.

3. Step 3: Identify error

   Leaf nodes should not be printed in left boundary function; they are printed separately in leaf traversal.

4. Final Answer:

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

5. Quick Check:

   Left boundary excludes leaves [OK]

Hint: Exclude leaf nodes in left boundary function [OK]

Common Mistakes:

• Printing leaf nodes in left or right boundary functions
• Not checking for NULL root
• Printing nodes in wrong order

5. Given a binary tree where some nodes have only one child, how should the boundary traversal be adapted to correctly include all boundary nodes without duplicates? Choose the best approach.

hard

A. Traverse all nodes in level order and print only those with one child

B. Traverse left and right boundaries including leaves, then print all leaves

C. Print all nodes in in-order traversal and remove duplicates afterwards

D. Traverse left boundary top-down excluding leaves, then all leaves left to right, then right boundary bottom-up excluding leaves, skipping duplicates

Solution

1. Step 1: Understand boundary traversal with single-child nodes

   Nodes with one child may appear in left or right boundary or as leaves.

2. Step 2: Avoid duplicates by excluding leaves in boundary traversals

   Left and right boundary traversals exclude leaves to avoid duplicates; leaves are printed separately.

3. Step 3: Combine traversals carefully

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

4. Final Answer:

   Traverse left boundary top-down excluding leaves, then all leaves left to right, then right boundary bottom-up excluding leaves, skipping duplicates -> Option D

5. Quick Check:

   Exclude leaves in boundaries, print leaves separately [OK]

Hint: Exclude leaves in boundaries, print leaves separately [OK]

Common Mistakes:

• Including leaves in both boundary and leaf traversals causing duplicates
• Ignoring nodes with single child in boundary
• Printing nodes in wrong order