Boundary Traversal of Binary Tree in DSA C - Deep Dive

Overview - Boundary Traversal of Binary Tree

What is it?

Boundary traversal of a binary tree means visiting all the nodes on the outer edge of the tree. This includes the left boundary, all the leaf nodes, and the right boundary in a specific order. The goal is to print these nodes without repetition, forming a boundary around the tree. It helps visualize the shape of the tree from the outside.

Why it matters

Without boundary traversal, we might miss understanding the outer shape of a tree, which is useful in many applications like graphical rendering, tree visualization, and solving problems that require edge information. It helps in extracting meaningful information about the tree's structure quickly. Without it, we would have to check every node individually to find the boundary, which is inefficient.

Where it fits

Before learning boundary traversal, you should understand binary trees, tree traversal methods like inorder, preorder, and postorder. After mastering boundary traversal, you can explore advanced tree algorithms like vertical order traversal, top view, and bottom view of trees.

Mental Model

Core Idea

Boundary traversal collects nodes along the outer edge of a binary tree by visiting the left boundary top-down, then all leaves left-to-right, and finally the right boundary bottom-up without duplicates.

Think of it like...

Imagine walking around a garden fence: you first walk along the left side, then walk around the flowers inside (leaves), and finally walk back along the right side to complete the loop.

Binary Tree Boundary Traversal

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

Traversal order:
Left Boundary: 1 -> 2 -> 4
Leaves: 4 -> 7 -> 8 -> 9 -> 10
Right Boundary (bottom-up): 6 -> 3

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

Build-Up - 8 Steps

1

Foundation

Understanding Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect with left and right children.

A binary tree is a structure where each node has up to two children: left and right. Each node stores a value and pointers to its children or null if none. For example, node 1 can have left child 2 and right child 3.

Result

You can visualize and represent a binary tree with nodes and their left/right links.

Understanding the basic structure of a binary tree is essential before exploring any traversal method.

2

Foundation

Basic Tree Traversals Review

Concept: Recall preorder, inorder, and postorder traversals to understand visiting nodes systematically.

Preorder visits root, then left subtree, then right subtree. Inorder visits left subtree, root, then right subtree. Postorder visits left subtree, right subtree, then root. These help us visit all nodes in different orders.

Result

You can visit all nodes in a tree in a controlled order.

Knowing these traversals helps understand how boundary traversal selectively visits nodes.

3

Intermediate

Identifying Left Boundary Nodes

🤔Before reading on: do you think the left boundary includes leaf nodes or only internal nodes? Commit to your answer.

Concept: Left boundary nodes are the nodes on the path from root to the leftmost leaf, excluding leaf nodes if they will be counted separately.

Start from the root and keep moving to the left child if it exists; otherwise, move to the right child. Add each visited node to the left boundary list except the leaf nodes, which will be added later.

Result

You get a list of nodes forming the left edge of the tree, top-down, excluding leaves.

Separating left boundary nodes from leaves prevents duplication and keeps traversal order clean.

4

Intermediate

Collecting Leaf Nodes Left to Right

🤔Before reading on: do you think leaf nodes are only at the bottom level or can they appear anywhere? Commit to your answer.

Concept: Leaf nodes are nodes without any children. Collect all leaf nodes by traversing the entire tree in a way that visits leaves from left to right.

Use a simple recursive traversal (like inorder) to visit every node. When a node has no left or right child, add it to the leaf list. This ensures all leaves are collected in left-to-right order.

Result

You get a list of all leaf nodes in the tree, ordered from leftmost leaf to rightmost leaf.

Collecting leaves separately ensures no leaf is missed and helps maintain the boundary traversal order.

5

Intermediate

Identifying Right Boundary Nodes Bottom-Up

🤔Before reading on: do you think the right boundary is collected top-down or bottom-up? Commit to your answer.

Concept: Right boundary nodes are the nodes on the path from root to the rightmost leaf, excluding leaf nodes, collected in reverse order (bottom-up).

Start from the root's right child and move to the right child if it exists; otherwise, move to the left child. Add nodes to a temporary list excluding leaves. After traversal, reverse this list to get bottom-up order.

Result

You get a list of right boundary nodes in bottom-up order, excluding leaves.

Reversing the right boundary nodes ensures the boundary traversal forms a continuous outer edge without repetition.

6

Advanced

Combining Boundaries Without Duplication

🤔Before reading on: do you think leaf nodes can appear in both left and right boundaries? Commit to your answer.

Concept: Combine left boundary, leaf nodes, and right boundary carefully to avoid printing any node twice.

Print the root node first. Then print left boundary nodes (excluding leaves). Next, print all leaf nodes. Finally, print right boundary nodes in bottom-up order. This order ensures no duplicates and a complete boundary.

Result

The final output is a list of nodes forming the boundary traversal of the tree.

Understanding how to merge these parts without overlap is key to correct boundary traversal.

7

Advanced

Implementing Boundary Traversal in C

Concept: Write a complete C program that performs boundary traversal using helper functions for left boundary, leaves, and right boundary.

Define a binary tree node struct. Implement functions: printLeftBoundary, printLeaves, printRightBoundary. In main traversal function, print root, call printLeftBoundary, printLeaves, and printRightBoundary in order. Use recursion for traversal.

Result

The program prints the boundary nodes in correct order for any binary tree input.

Seeing the full implementation clarifies how the parts work together in code.

8

Expert

Handling Edge Cases and Optimization

🤔Before reading on: do you think a tree with only left or only right children needs special handling? Commit to your answer.

Concept: Consider trees with no left or right subtree, single-node trees, and optimize to avoid unnecessary recursion.

Check if root is leaf to avoid duplication. In left/right boundary functions, skip nodes that are leaves. Optimize leaf collection to avoid revisiting nodes. Handle skewed trees where left or right boundary might overlap with leaves.

Result

The traversal works correctly and efficiently for all tree shapes.

Anticipating and handling edge cases prevents bugs and improves performance in real-world use.

Under the Hood

Boundary traversal works by splitting the tree into three parts: left boundary, leaves, and right boundary. It uses recursive calls to explore these parts separately. The left boundary is collected by always choosing the left child first, the leaves by checking nodes with no children, and the right boundary by choosing the right child first and reversing the collected nodes. This avoids duplication and maintains order.

Why designed this way?

This design ensures a clear, ordered traversal of the tree's outer edge without revisiting nodes. Alternatives like a single traversal with complex conditions would be harder to implement and less readable. Separating concerns simplifies logic and debugging.

Boundary Traversal Mechanism

Root
 │
 ├─ Left Boundary (top-down)
 │    ├─ Node
 │    ├─ Node
 │    └─ ...
 ├─ Leaves (left to right)
 │    ├─ Leaf Node
 │    ├─ Leaf Node
 │    └─ ...
 └─ Right Boundary (bottom-up)
      ├─ Node
      ├─ Node
      └─ ...

Myth Busters - 3 Common Misconceptions

Quick: Do you think leaf nodes are part of both left and right boundaries? Commit yes or no.

Common Belief: Leaf nodes are included in both left and right boundaries.

Reality: Leaf nodes are collected separately and should not be duplicated in left or right boundaries.

Why it matters: Including leaves in both boundaries causes duplicate nodes in the output, breaking the boundary traversal correctness.

Quick: Is the right boundary collected top-down like the left boundary? Commit yes or no.

Common Belief: Right boundary nodes are collected top-down just like left boundary nodes.

Reality: Right boundary nodes are collected bottom-up to maintain the correct traversal order.

Why it matters: Collecting right boundary top-down reverses the boundary order and breaks the continuous outer edge sequence.

Quick: Can boundary traversal be done with a single simple traversal? Commit yes or no.

Common Belief: Boundary traversal can be done with one simple traversal visiting nodes once.

Reality: Boundary traversal requires separate passes for left boundary, leaves, and right boundary to avoid duplication and maintain order.

Why it matters: Trying a single traversal leads to complex conditions and often incorrect or duplicated output.

Expert Zone

1

Left and right boundary traversals must exclude leaf nodes to prevent duplication with leaf collection.

2

In skewed trees (all left or all right), boundaries and leaves overlap, requiring careful checks to avoid repeated nodes.

3

Reversing the right boundary after collection is crucial; forgetting this breaks the traversal order.

When NOT to use

Boundary traversal is not suitable when you need full tree traversal or specific node orderings like inorder or level order. For those, use standard traversals. Also, for very large trees where memory is limited, boundary traversal's multiple passes may be inefficient.

Production Patterns

Boundary traversal is used in graphical tree visualization tools to outline tree shapes, in algorithms that require edge node processing like network routing trees, and in coding interviews to test understanding of tree traversal variations.

Connections

Graph Perimeter Detection

Boundary traversal in trees is similar to finding the perimeter or outer edges in graph structures.

Understanding boundary traversal helps grasp how to detect edges in more complex graph data structures.

Convex Hull in Computational Geometry

Both find the outer boundary enclosing a set of points or nodes.

Knowing boundary traversal aids in understanding how algorithms like convex hull identify outer points in geometry.

Human Visual Perception of Shapes

Boundary traversal mimics how humans perceive the outline of objects to recognize shapes.

This connection shows how computer algorithms can model natural perception processes.

Common Pitfalls

#1 Including leaf nodes in both left and right boundary lists causes duplicates.

Wrong approach:

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

void printLeaves(Node* node) {
if (node == NULL) return;
if (!node->left && !node->right) printf("%d ", node->data);
printLeaves(node->left);
printLeaves(node->right);
}

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

Correct approach:

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

void printLeaves(Node* node) {
if (node == NULL) return;
printLeaves(node->left);
if (!node->left && !node->right) printf("%d ", node->data);
printLeaves(node->right);
}

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

Root cause:

Not checking if a node is a leaf before printing causes leaf nodes to be printed multiple times.

#2 Printing right boundary nodes in top-down order instead of bottom-up.

Wrong approach:

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

Correct approach:

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

Root cause:

Printing before recursive calls causes the order to be top-down instead of bottom-up.

#3 Not handling single-node or skewed trees causing missing or duplicate nodes.

Wrong approach:

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

Correct approach:

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

Root cause:

Not checking if root is leaf causes duplication or missing nodes in edge cases.

Key Takeaways

Boundary traversal visits the outer edge of a binary tree by combining left boundary, leaves, and right boundary nodes in a specific order.

Separating the traversal into three parts prevents duplication and maintains the correct sequence of nodes.

Right boundary nodes must be collected bottom-up, which is different from the left boundary's top-down order.

Handling edge cases like skewed trees and single-node trees is essential for correct traversal.

Understanding boundary traversal deepens your grasp of tree structures and prepares you for advanced tree algorithms.

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