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, leaves, then right edge.

Analogy: Imagine walking around the outside of a garden fence, first along the left side, then around the bottom plants, and finally up the right side to return 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 in order

Goal: Print nodes on the boundary of the tree in anti-clockwise order starting from root

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 edge nodes form the first boundary side

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 the boundary but not included in left or right edges

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 form the last boundary side in reverse order

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

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

bool isLeaf(Node* node) {
    return node && !node->left && !node->right;
}

void addLeftBoundary(Node* root, vector<int>& res) {
    Node* curr = root->left;
    while (curr) {
        if (!isLeaf(curr)) res.push_back(curr->data); // add non-leaf left boundary
        if (curr->left) curr = curr->left; // go left if possible
        else curr = curr->right; // else go right
    }
}

void addLeaves(Node* root, vector<int>& res) {
    if (!root) return;
    if (isLeaf(root)) {
        res.push_back(root->data); // add leaf node
        return;
    }
    addLeaves(root->left, res); // traverse left subtree
    addLeaves(root->right, res); // traverse right subtree
}

void addRightBoundary(Node* root, vector<int>& res) {
    Node* curr = root->right;
    vector<int> tmp;
    while (curr) {
        if (!isLeaf(curr)) tmp.push_back(curr->data); // add non-leaf right boundary
        if (curr->right) curr = curr->right; // go right if possible
        else curr = curr->left; // else go left
    }
    for (int i = (int)tmp.size() - 1; i >= 0; i--) {
        res.push_back(tmp[i]); // add right boundary in reverse
    }
}

vector<int> boundaryTraversal(Node* root) {
    vector<int> res;
    if (!root) return res;
    if (!isLeaf(root)) res.push_back(root->data); // add root if not leaf
    addLeftBoundary(root, res); // add left boundary
    addLeaves(root, res); // add leaves
    addRightBoundary(root, res); // add right boundary
    return res;
}

int 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);

    vector<int> boundary = boundaryTraversal(root);
    for (int val : boundary) {
        cout << val << " -> ";
    }
    cout << "null" << endl;
    return 0;
}

if (!isLeaf(root)) res.push_back(root->data);

Add root node if it is not a leaf

Node* curr = root->left; while (curr) { if (!isLeaf(curr)) res.push_back(curr->data); if (curr->left) curr = curr->left; else curr = curr->right; }

Traverse and add left boundary nodes excluding leaves

if (isLeaf(root)) { res.push_back(root->data); return; } addLeaves(root->left, res); addLeaves(root->right, res);

Add all leaf nodes from left to right

Node* curr = root->right; vector<int> tmp; while (curr) { if (!isLeaf(curr)) tmp.push_back(curr->data); if (curr->right) curr = curr->right; else curr = curr->left; } for (int i = (int)tmp.size() - 1; i >= 0; i--) { res.push_back(tmp[i]); }

Traverse right boundary excluding leaves and add in reverse order

Output

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

Complexity Analysis

Time: O(n) because we visit each node at most once during boundary traversal

Space: O(n) for storing the boundary nodes in the result list and temporary storage for right boundary

vs Alternative: Compared to traversing the tree multiple times or checking all nodes repeatedly, this approach efficiently collects boundary nodes in a single pass with clear separation of parts

Edge Cases

Empty tree

Returns empty boundary list

DSA C++

if (!root) return res;

Tree with only root node

Returns list with only root node

DSA C++

if (!isLeaf(root)) res.push_back(root->data);

Tree with only left subtree

Left boundary and leaves are added correctly, right boundary empty

DSA C++

Node* curr = root->left; while (curr) { ... }

Tree with only right subtree

Right boundary and leaves are added correctly, left boundary empty

DSA C++

Node* curr = root->right; vector<int> tmp; while (curr) { ... }

When to Use This Pattern

When asked to print or collect the outer nodes of a binary tree in a specific order, use boundary traversal to separate left edge, leaves, and right edge for clear and complete coverage.

Common Mistakes

Mistake: Including leaf nodes twice by adding them in left or right boundary traversal as well as leaf traversal
Fix: Skip leaf nodes when adding left and right boundaries, add leaves separately

Mistake: Adding right boundary nodes in top-down order instead of bottom-up
Fix: Store right boundary nodes temporarily and add them in reverse order

Summary

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

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

Separate the traversal into left boundary, leaves, and right boundary to avoid duplicates and maintain order.