Boundary Traversal Algorithm

The **Boundary Traversal** of a Binary Tree is a popular interview algorithm (e.g., LeetCode 545). It visits all the boundary nodes in an **anti-clockwise** path, starting from the root.

PART 1

The Root Node

The traversal always starts by visiting the Root node, which serves as the origin.

PART 2

Left Boundary

Traverse down using `node.left` (or `node.right` if left is empty). **Exclude leaf nodes** to avoid duplicates.

PART 3

Leaf Nodes

Collect all leaves from **left to right** using a recursive standard pre-order/in-order depth-first traversal.

PART 4

Right Boundary

Traverse down the right side (excluding leaves), but **reverse them** (bottom-up) before adding to result.

Algorithm Implementation

import java.util.*;

class Node {
    int data;
    Node left, right;
    Node(int data) {
        this.data = data;
    }
}

public class BoundaryTraversal {
    public List<Integer> boundary(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        // Part 1: Root Node
        if (!isLeaf(root)) result.add(root.data);
        
        // Part 2: Left Boundary
        addLeftBoundary(root.left, result);
        
        // Part 3: Leaf Nodes
        addLeaves(root, result);
        
        // Part 4: Right Boundary
        addRightBoundary(root.right, result);
        
        return result;
    }
    
    private boolean isLeaf(Node node) {
        return node != null && node.left == null && node.right == null;
    }
    
    private void addLeftBoundary(Node curr, List<Integer> res) {
        while (curr != null) {
            if (!isLeaf(curr)) res.add(curr.data);
            curr = (curr.left != null) ? curr.left : curr.right;
        }
    }
    
    private void addLeaves(Node curr, List<Integer> res) {
        if (curr == null) return;
        if (isLeaf(curr)) {
            res.add(curr.data);
            return;
        }
        addLeaves(curr.left, res);
        addLeaves(curr.right, res);
    }
    
    private void addRightBoundary(Node curr, List<Integer> res) {
        List<Integer> temp = new ArrayList<>();
        while (curr != null) {
            if (!isLeaf(curr)) temp.add(curr.data);
            curr = (curr.right != null) ? curr.right : curr.left;
        }
        // Add elements to result in reverse order (bottom-up)
        for (int i = temp.size() - 1; i >= 0; i--) {
            res.add(temp.get(i));
        }
    }
}

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

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

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

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

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

    void addRightBoundary(Node* curr, vector<int>& res) {
        vector<int> temp;
        while (curr) {
            if (!isLeaf(curr)) temp.push_back(curr->data);
            curr = (curr->right) ? curr->right : curr->left;
        }
        // Reverse order push
        for (int i = temp.size() - 1; i >= 0; --i) {
            res.push_back(temp[i]);
        }
    }

public:
    vector<int> boundary(Node* root) {
        vector<int> result;
        if (!root) return result;

        // Part 1: Root Node
        if (!isLeaf(root)) result.push_back(root->data);

        // Part 2: Left Boundary
        addLeftBoundary(root->left, result);

        // Part 3: Leaves (L to R)
        addLeaves(root, result);

        // Part 4: Right Boundary (Bottom-up)
        addRightBoundary(root->right, result);

        return result;
    }
};

class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

class Solution:
    def isLeaf(self, node):
        return node is not None and node.left is None and node.right is None

    def addLeftBoundary(self, root, res):
        curr = root.left
        while curr:
            if not self.isLeaf(curr):
                res.append(curr.data)
            curr = curr.left if curr.left else curr.right

    def addLeaves(self, curr, res):
        if not curr:
            return
        if self.isLeaf(curr):
            res.append(curr.data)
            return
        self.addLeaves(curr.left, res)
        self.addLeaves(curr.right, res)

    def addRightBoundary(self, root, res):
        curr = root.right
        temp = []
        while curr:
            if not self.isLeaf(curr):
                temp.append(curr.data)
            curr = curr.right if curr.right else curr.left
        # Reverse to get bottom-up
        res.extend(temp[::-1])

    def boundary(self, root):
        res = []
        if not root:
            return res
        
        # Part 1: Root Node
        if not self.isLeaf(root):
            res.append(root.data)
            
        # Part 2: Left Boundary
        self.addLeftBoundary(root, res)
        
        # Part 3: Leaves (L to R)
        self.addLeaves(root, res)
        
        # Part 4: Right Boundary (Bottom-up)
        self.addRightBoundary(root, res)
        
        return res

Boundary Traversal of Binary Tree

Tree Shape Presets

Traversal Result