Boundary Traversal of Binary Tree

Problem Link

Boundary Traversal of Binary Tree – GeeksforGeeks

Problem: Boundary Traversal of Binary Tree

Problem Statement

Given a binary tree, return a list containing the boundary traversal of the tree in anti-clockwise direction starting from the root.

Boundary includes:

1. Left Boundary (excluding leaves)

2. All Leaf Nodes (left to right)

3. Right Boundary (excluding leaves, in bottom-up order)

Examples

Example 1

Input: 
        1
       / \
      2   3
     / \   \
    4   5   6

Output: 
[1, 2, 4, 5, 6, 3]

Example 2

Input:
        1
       / \
      2   3
       \
        4

Output:
[1, 2, 4, 3]

Constraints

• 1 <= Number of nodes <= 10⁴

• 1 <= Node.data <= 10⁵

Intuition

Boundary traversal in anti-clockwise direction includes:

• The left boundary (top-down), excluding leaves

• The leaf nodes from left to right

• The right boundary (bottom-up), excluding leaves

We must treat each component separately and avoid adding duplicate nodes (especially leaves).

Approach

1. Add root node to the result (if it's not a leaf)

2. Add left boundary nodes:

   • Traverse from root.left down the left edge

   • Stop before adding leaf nodes

3. Add all leaves:

   • Do a complete DFS and add leaves

4. Add right boundary nodes:

   • Traverse from root.right down the right edge

   • Stop before adding leaf nodes

   • Store in temporary list and reverse it for bottom-up order

Code (Java)

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

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

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

    void addRightBoundary(Node node, ArrayList<Integer> res) {
        Node curr = node.right;
        Stack<Integer> stack = new Stack<>();
        while (curr != null) {
            if (!isLeaf(curr)) stack.push(curr.data);
            if (curr.right != null) curr = curr.right;
            else curr = curr.left;
        }
        while (!stack.isEmpty()) {
            res.add(stack.pop());
        }
    }

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

Time and Space Complexity

• Time Complexity: O(N)
  Every node is visited exactly once.

• Space Complexity: O(H) for recursive calls (H = height), and O(N) for output list and stack.

Dry Run

Tree:

        1
       / \
      2   3
     / \   \
    4   5   6

Left Boundary: 2  
Leaves: 4, 5, 6  
Right Boundary (bottom-up): 3

Output: [1, 2, 4, 5, 6, 3]

Conclusion

• The boundary traversal problem is a combination of multiple tree traversals: left boundary, leaves, and right boundary.

• It's important to handle edge cases like single-node trees, skewed trees, and leaf duplications carefully.

• This pattern is useful in various advanced tree traversal problems involving non-standard orders.