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.

Practice

1. What does the boundary traversal of a binary tree include?

easy

A. Left boundary, leaves, and right boundary nodes in order

B. Only leaf nodes from left to right

C. All nodes in level order

D. Only root and leaf nodes

Solution

1. Step 1: Understand boundary traversal components

   Boundary traversal includes the left boundary (excluding leaves), all leaf nodes, and the right boundary (excluding leaves) in reverse order.

2. Step 2: Combine all parts in order

   Traverse left boundary top-down, then leaves left to right, then right boundary bottom-up to get the full boundary traversal.

3. Final Answer:

   Left boundary, leaves, and right boundary nodes in order -> Option A

4. Quick Check:

   Boundary traversal = Left boundary + Leaves + Right boundary [OK]

Hint: Remember: left boundary + leaves + right boundary [OK]

Common Mistakes:

• Including leaf nodes twice in left or right boundary
• Ignoring right boundary order (should be bottom-up)
• Confusing boundary traversal with level order

2. Which of the following C++ function signatures is correct for printing the left boundary of a binary tree?

easy

A. void printLeftBoundary(Node* root);

B. int printLeftBoundary(Node root);

C. void printLeftBoundary(Node root);

D. int printLeftBoundary(Node* root);

Solution

1. Step 1: Identify correct parameter type for tree node

   Binary tree nodes are passed as pointers (Node*), not by value (Node), to avoid copying the entire subtree.

2. Step 2: Check return type for printing function

   Printing functions usually return void as they output directly and do not return a value.

3. Final Answer:

   void printLeftBoundary(Node* root); -> Option A

4. Quick Check:

   Pointer parameter + void return = correct signature [OK]

Hint: Use pointer parameter and void return for print functions [OK]

Common Mistakes:

• Passing node by value causing unnecessary copies
• Using int return type for printing functions
• Missing pointer symbol (*) in parameter

3. Given the binary tree below, what is the boundary traversal output?

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

medium

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

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

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

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

Solution

1. Step 1: Identify left boundary nodes excluding leaves

   Left boundary: 1, 2 (4 is leaf, so excluded here)

2. Step 2: Collect all leaf nodes left to right

   Leaves: 4, 7, 8, 9

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

   Right boundary: 6, 3

4. Step 4: Combine all parts

   Boundary traversal = [1, 2] + [4, 7, 8, 9] + [6, 3] = [1, 2, 4, 7, 8, 9, 6, 3]

5. Final Answer:

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

6. Quick Check:

   Left boundary + leaves + right boundary = [1, 2, 4, 7, 8, 9, 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 code snippet is intended to print the right boundary of a binary tree. What is the error?

void printRightBoundary(Node* root) {
    if (!root) return;
    if (root->right) {
        printRightBoundary(root->right);
    } else if (root->left) {
        printRightBoundary(root->left);
    }
    std::cout << root->data << " ";
}

medium

A. It misses printing the root node

B. It does not print nodes in bottom-up order

C. It prints leaf nodes which should be excluded

D. It causes infinite recursion

Solution

1. Step 1: Analyze printing condition in recursion

   The function prints every node after recursive calls, including leaf nodes which should be excluded from right boundary printing.

2. Step 2: Identify missing leaf node check

   There is no check to skip printing leaf nodes, so leaf nodes get printed incorrectly as part of right boundary.

3. Final Answer:

   It prints leaf nodes which should be excluded -> Option C

4. Quick Check:

   Leaf nodes must be excluded from right boundary [OK]

Hint: Skip printing leaf nodes in boundary functions [OK]

Common Mistakes:

• Printing leaf nodes in boundary traversal
• Not checking for null nodes before recursion
• Confusing order of printing nodes

5. You want to perform boundary traversal on a binary tree that may have only one node or be skewed (all left or all right). Which approach correctly handles these edge cases?

hard

A. Print only leaf nodes as boundary in skewed trees

B. Print all nodes in level order to cover all cases

C. Print left boundary including leaves, then right boundary including leaves, ignoring root

D. Print root, then left boundary excluding leaves, then leaves, then right boundary excluding leaves, skipping duplicates

Solution

1. Step 1: Understand edge cases in boundary traversal

   Single node tree or skewed trees may cause duplicates if leaves are included in boundaries without checks.

2. Step 2: Use approach that prints root, left boundary excluding leaves, leaves, right boundary excluding leaves, and skip duplicates

   This ensures no node is printed twice and all edge cases are handled correctly.

3. Final Answer:

   Print root, then left boundary excluding leaves, then leaves, then right boundary excluding leaves, skipping duplicates -> Option D

4. Quick Check:

   Exclude leaves in boundaries + skip duplicates [OK]

Hint: Exclude leaves in boundaries and skip duplicates [OK]

Common Mistakes:

• Printing leaves twice in skewed trees
• Ignoring root node in traversal
• Using level order which is not boundary traversal