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 list all family members who are on the outer edge of this tree, starting from the top ancestor, then the left side members, the leaf members, and finally the right side members in reverse order.

🎯 Goal: Build a program that performs a boundary traversal of a binary tree. The traversal should print the nodes on the boundary in this order: root, left boundary (excluding leaves), all leaves (left to right), and right boundary (excluding leaves) in reverse order.

📋 What You'll Learn

Create a binary tree with the exact structure given

Implement functions to print the left boundary, leaves, and right boundary

Combine these functions to perform the boundary traversal

Print the boundary traversal nodes in one line separated by spaces

💡 Why This Matters

🌍 Real World

Boundary traversal helps in graphical rendering of tree edges, network topology visualization, and understanding hierarchical data boundaries.

💼 Career

Understanding tree traversals and boundary conditions is essential for software engineers working with data structures, algorithms, and system design.

1

Create the Binary Tree Structure

Create a struct called Node with an int data, and two pointers left and right. Then create the exact binary tree with root node having value 20, left child 8, right child 22, left child's left child 4, left child's right child 12, right child's right child 25, and left child's right child's left child 10 and left child's right child's right child 14.

DSA C++

// Define struct Node
// Create the binary tree with root 20 and the exact children
// Your code here

Hint

Define the Node struct with a constructor for easy node creation. Then link nodes exactly as described.

2

Add Helper Functions to Check Leaf Nodes

Add a function called isLeaf that takes a Node* and returns true if the node has no left and right children, otherwise false.

DSA C++

#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

bool isLeaf(Node* node) {
    // Your code here
}

int main() {
    Node* 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->right->right = new Node(25);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(14);
    return 0;
}

Hint

Check if both left and right pointers are nullptr.

3

Implement Boundary Traversal Helper Functions

Implement three functions: printLeftBoundary(Node* root), printLeaves(Node* root), and printRightBoundary(Node* root). - printLeftBoundary should print the left boundary nodes excluding leaves, top-down. - printLeaves should print all leaf nodes from left to right. - printRightBoundary should print the right boundary nodes excluding leaves, bottom-up. Use cout to print node data followed by a space.

DSA C++

    Node* curr = root->left;
    while (curr) {
        if (!isLeaf(curr)) cout data left) curr = curr->left;
        else curr = curr->right;
    }
    if (root == nullptr) return;
    if (isLeaf(root)) {
        cout data left);
    printLeaves(root->right);
    Node* curr = root->right;
    int stack[100];
    int top = -1;
    while (curr) {
        if (!isLeaf(curr)) stack[++top] = curr->data;
        if (curr->right) curr = curr->right;
        else curr = curr->left;
    }
    while (top >= 0) {
        cout << stack[top--] << " ";
    }

Hint

Use loops for left and right boundaries and recursion for leaves. Store right boundary nodes in a stack to print in reverse.

4

Perform and Print the Boundary Traversal

In main(), print the root node's data followed by a space. Then call printLeftBoundary(root), printLeaves(root), and printRightBoundary(root) in this order to print the full boundary traversal on one line.

DSA C++

Hint

Print root first, then call the three helper functions in order to print the boundary traversal.