L20. Boundary Traversal in Binary Tree | C++ | Java

Boundary traversal of a binary tree requires printing the outer perimeter of the tree in a strict anti-clockwise direction. This journey starts from the root, travels down the left boundary, traverses across all leaf nodes from left to right, and climbs back up the right boundary in reverse order, finishing back at the root.

1. Why Do We Need Boundary Traversal?

Standard tree traversals like Level Order (BFS) or Depth-First Search (Preorder, Inorder, Postorder) visit every node in the tree systematically based on depth or levels. However, certain structural problems require isolating the outer perimeter (the frame) of a data structure.

The Problem: Given an arbitrary binary tree, extract all nodes that form its outer boundary in counter-clockwise order without duplicating corner nodes.
The Challenge: Standard traversals cannot isolate this perimeter cleanly. We need a targeted strategy that separates the perimeter into three distinct geometrical segments.

2. Core Mental Model: The Perimeter Walk

Imagine walking along the outer edge of a tree park in an anti-clockwise loop:

Start at the Gate (Root): Stand at the top root node.
Walk Down the Left Wall: Move down the leftmost edge, ignoring any inner branches or leaf nodes along this wall.
Walk Across the Base (Leaves): Scrape across all the bottom-most leaf nodes from left to right.
Walk Up the Right Wall (in Reverse): Climb back up the rightmost edge from the bottom to the top, collecting nodes in reverse order so they connect seamlessly back to the root.

CODE

       [Root: 1]
      /         \
   (Left)     (Right)
   Boundary   Boundary
    /             \
  [2]             [7]
  /                 \
[3]                 [8]
  \                   \
  [4]                 [9]
    \                 /
   [5 (Leaf)]   [11 (Leaf)]  [10 (Leaf)]
     \             /
      (Leaf Nodes across bottom)

3. The Three-Step Algorithmic Strategy

To compute the anti-clockwise boundary traversal cleanly, decompose the problem into three sequential operations:

Left Boundary (Excluding Leaves): Start from root->left. Traverse downward by always preferring the left child. If a left child does not exist, fall back to the right child. Stop when encountering a leaf node.
Leaf Nodes (Inorder Traversal): Traverse the entire tree using an Inorder Traversal (Left -> Root -> Right). Whenever a node is identified as a leaf (having neither left nor right children), add it to the collection.
Right Boundary (Reverse Order, Excluding Leaves): Start from root->right. Traverse downward by always preferring the right child. If a right child does not exist, fall back to the left child. Stop when encountering a leaf node. Store these nodes in a temporary stack or vector, then reverse them so they flow upward.

Note: Always add the root node first to the data structure. To avoid duplicate entries (especially in single-node trees or skewed trees), explicitly check that a node is not a leaf before inserting it into the left or right boundary collections.

4. Step-by-Step Flow Walkthrough

Consider a binary tree with nodes 1 through 11:

Initial Check: If the root is null, return an empty list. Add root (1) to the answer list.
Left Boundary Collection:
- Start at root->left (2). Not a leaf -> Add 2.
- Move to 2->left (3). Not a leaf -> Add 3.
- 3 has no left child. Fall back to right child (4). Not a leaf -> Add 4.
- 4->left is 5. 5 is a leaf node -> Stop.
- Left boundary collected: [1, 2, 3, 4]
Leaf Node Collection (Inorder):
- Traverse the tree, checking isLeaf().
- Leaves encountered in left-to-right order: 5, 6, 10, 11.
- Leaves collected: [5, 6, 10, 11]
Right Boundary Collection:
- Start at root->right (7). Not a leaf -> Add to temp [7].
- Move to 7->right (8). Not a leaf -> Add to temp [7, 8].
- 8 has no right child. Fall back to left child (9). Not a leaf -> Add to temp [7, 8, 9].
- 9->right is a leaf node -> Stop.
- Reverse temp collection ([7, 8, 9] -> [9, 8, 7]).
- Right boundary collected: [9, 8, 7]
Final Merged Result: [1, 2, 3, 4, 5, 6, 10, 11, 9, 8, 7]

5. Complete C++ Implementation

C++

#include <bits/stdc++.h>
using namespace std;

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

class Solution {
private:
    bool isLeaf(Node* root) {
        return !root->left && !root->right;
    }

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

    void addRightBoundary(Node* root, vector<int>& res) {
        Node* curr = root->right;
        vector<int> temp;
        while (curr) {
            if (!isLeaf(curr)) temp.push_back(curr->data);
            if (curr->right) curr = curr->right;
            else curr = curr->left;
        }
        // Reverse the right boundary to make it bottom-up
        for (int i = temp.size() - 1; i >= 0; --i) {
            res.push_back(temp[i]);
        }
    }

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

public:
    vector<int> boundaryTraversal(Node* root) {
        vector<int> res;
        if (!root) return res;
        
        // 1. Add root if it's not a leaf
        if (!isLeaf(root)) res.push_back(root->data);
        
        // 2. Add Left Boundary excluding leaves
        addLeftBoundary(root, res);
        
        // 3. Add all Leaf Nodes via Inorder traversal
        addLeaves(root, res);
        
        // 4. Add Right Boundary in reverse order excluding leaves
        addRightBoundary(root, res);
        
        return res;
    }
};

6. Complete Java Implementation

JAVA

import java.util.ArrayList;
import java.util.List;

class Node {
    int data;
    Node left, right;
    Node(int val) {
        data = val;
        left = right = null;
    }
}

class Solution {
    boolean isLeaf(Node root) {
        return root.left == null && root.right == null;
    }

    void addLeftBoundary(Node root, List<Integer> res) {
        Node curr = root.left;
        while (curr != null) {
            if (!isLeaf(curr)) res.add(curr.data);
            if (curr.left != null) curr = curr.left;
            else curr = curr.right;
        }
    }

    void addRightBoundary(Node root, List<Integer> res) {
        Node curr = root.right;
        List<Integer> temp = new ArrayList<>();
        while (curr != null) {
            if (!isLeaf(curr)) temp.add(curr.data);
            if (curr.right != null) curr = curr.right;
            else curr = curr.left;
        }
        // Reverse right boundary
        for (int i = temp.size() - 1; i >= 0; i--) {
            res.add(temp.get(i));
        }
    }

    void addLeaves(Node root, List<Integer> res) {
        if (root == null) return;
        if (isLeaf(root)) {
            res.add(root.data);
            return;
        }
        addLeaves(root.left, res);
        addLeaves(root.right, res);
    }

    List<Integer> boundaryTraversal(Node node) {
        List<Integer> res = new ArrayList<>();
        if (node == null) return res;
        
        if (!isLeaf(node)) res.add(node.data);
        
        addLeftBoundary(node, res);
        addLeaves(node, res);
        addRightBoundary(node, res);
        
        return res;
    }
}

7. Complexity Analysis

Phase / Operation	Time Complexity	Space Complexity	Rationale
Left Boundary	$O(H)$	$O(1)$ auxiliary	Traversals follow height $H$ of the tree.
Leaf Traversal	$O(N)$	$O(H)$ recursive stack	Standard Inorder traversal visits every node once.
Right Boundary	$O(H)$	$O(H)$ temporary storage	Height-bound traversal with vector reversal.
Overall Algorithm	$O(N)$	$O(N)$	Dominated by visiting all $N$ nodes for leaves and storing output of size $N$ .

Note: The auxiliary space complexity for the algorithm execution is proportional to the height of the tree $O(H)$ due to recursive stack frames during leaf collection. The output vector stores up to $N$ elements, but return data structures are generally excluded from auxiliary space evaluations.

Summary and Key Takeaways

Definition: Boundary traversal prints a binary tree's perimeter in strict anti-clockwise order.
Three Core Phases: Left boundary (excluding leaves) $\rightarrow$ Leaf nodes (left-to-right) $\rightarrow$ Right boundary in reverse (excluding leaves).
Fallback Navigation: When traversing the left boundary, always prioritize left. If left is null, take right. Mirror this for the right boundary (right first, fallback to left).
Leaf Exclusion: Both left and right boundary helper functions must check isLeaf(curr) to avoid duplicating nodes collected during the leaf traversal phase.
Leaf Traversal Order: Always use an Inorder Traversal (Left -> Root -> Right) to gather leaf nodes to guarantee left-to-right sequencing.
Reversal Requirement: The right boundary must be collected into a temporary buffer and reversed so that nodes appear bottom-up (ascending toward the root).
Time & Space: Operates in linear time $O(N)$ with recursion stack space bounded by the tree height $O(H)$ .