Boundary Traversal of Binary Tree in DSA Java

Mental Model

We want to visit all the nodes on the edges of a tree in a specific order: left edge, leaves, then right edge.

Analogy: Imagine walking around the outside of a garden shaped like a tree, touching all the plants on the boundary without going inside.

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

Boundary nodes are: 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: left boundary, leaves, right boundary

Goal: Print all boundary nodes in anti-clockwise order starting from root

Step 1: Add root node 1 to result

Result: 1

Why: Root is always part of boundary

Step 2: Traverse left boundary excluding leaves: add 2

Result: 1 -> 2

Why: Left boundary nodes are on the left edge, excluding leaves to avoid duplicates

Step 3: Traverse leaves from left subtree: add 4, 7 and 8

Result: 1 -> 2 -> 4 -> 7 -> 8

Why: Leaves are nodes with no children, added after left boundary

Step 4: Traverse leaves from right subtree: add 9

Result: 1 -> 2 -> 4 -> 7 -> 8 -> 9

Why: Add leaves from right subtree to complete leaf nodes

Step 5: Traverse right boundary excluding leaves in bottom-up order: add 6 then 3

Result: 1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3

Why: Right boundary nodes added in reverse to maintain anti-clockwise order

Result:

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

Annotated Code

DSA Java

import java.util.*;

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

public class BoundaryTraversal {

    // Check if node is leaf
    static boolean isLeaf(Node node) {
        return node.left == null && node.right == null;
    }

    // Add left boundary excluding leaves
    static void addLeftBoundary(Node node, List<Integer> res) {
        Node curr = node.left;
        while (curr != null) {
            if (!isLeaf(curr)) res.add(curr.data); // add if not leaf
            if (curr.left != null) curr = curr.left; // go left if possible
            else curr = curr.right; // else go right
        }
    }

    // Add leaf nodes
    static void addLeaves(Node node, List<Integer> res) {
        if (node == null) return;
        if (isLeaf(node)) {
            res.add(node.data); // add leaf
            return;
        }
        addLeaves(node.left, res); // recurse left
        addLeaves(node.right, res); // recurse right
    }

    // Add right boundary excluding leaves in reverse order
    static void addRightBoundary(Node node, List<Integer> res) {
        Node curr = node.right;
        Stack<Integer> stack = new Stack<>();
        while (curr != null) {
            if (!isLeaf(curr)) stack.push(curr.data); // add if not leaf
            if (curr.right != null) curr = curr.right; // go right if possible
            else curr = curr.left; // else go left
        }
        while (!stack.isEmpty()) {
            res.add(stack.pop()); // add in reverse
        }
    }

    static List<Integer> boundaryTraversal(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        res.add(root.data); // add root regardless of leaf or not

        addLeftBoundary(root, res); // add left boundary
        addLeaves(root, res); // add leaves
        addRightBoundary(root, res); // add right boundary

        return res;
    }

    public static void main(String[] args) {
        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.right = new Node(9);

        List<Integer> boundary = boundaryTraversal(root);
        for (int val : boundary) {
            System.out.print(val + " -> ");
        }
        System.out.print("null\n");
    }
}

res.add(root.data);

Add root node regardless of leaf status to include single node tree correctly

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; }

Traverse left boundary excluding leaves, moving down left or right child

if (isLeaf(node)) { res.add(node.data); return; } addLeaves(node.left, res); addLeaves(node.right, res);

Add all leaf nodes by recursive traversal

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()); }

Traverse right boundary excluding leaves, store in stack, then 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 traversal

Space: O(n) for the output list and recursion stack in worst case

vs Alternative: Compared to naive approach of checking all nodes multiple times, this is efficient with single pass for boundaries and leaves

Edge Cases

Empty tree

Returns empty list without error

DSA Java

if (root == null) return res;

Tree with single node

Returns list with only root node

DSA Java

res.add(root.data);

Tree with only left subtree

Left boundary and leaves are added correctly, right boundary empty

DSA Java

addRightBoundary(root, res);

Tree with only right subtree

Right boundary and leaves added correctly, left boundary empty

DSA Java

addLeftBoundary(root, res);

When to Use This Pattern

When asked to print nodes on the edge of a binary tree in a specific order, use boundary traversal to collect left boundary, leaves, and right boundary separately.

Common Mistakes

Mistake: Including leaf nodes twice by adding them in both boundary and leaf traversals
Fix: Exclude leaves from left and right boundary traversals by checking isLeaf before adding

Mistake: Adding right boundary nodes in top-down order causing wrong output order
Fix: Use a stack to add right boundary nodes in bottom-up order

Summary

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

Use when you need to visit only the outer edge nodes of a tree.

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

Practice

1. What is the correct order of nodes visited in a boundary traversal of a binary tree?

easy

A. Root, leaves (left to right), left boundary (top-down), right boundary (bottom-up)

B. Leaves (left to right), root, left boundary (top-down), right boundary (bottom-up)

C. Root, left boundary (top-down), leaves (left to right), right boundary (bottom-up)

D. Left boundary (top-down), root, right boundary (bottom-up), leaves (left to right)

Solution

1. Step 1: Understand boundary traversal parts

   Boundary traversal visits root, then left boundary top-down, then leaves left to right, then right boundary bottom-up.

2. Step 2: Arrange traversal order

   Root is first, left boundary next, leaves after that, and right boundary last in reverse order.

3. Final Answer:

   Root, left boundary (top-down), leaves (left to right), right boundary (bottom-up) -> Option C

4. Quick Check:

   Boundary traversal order = Root + Left + Leaves + Right [OK]

Hint: Remember: Root, Left boundary, Leaves, Right boundary [OK]

Common Mistakes:

• Mixing order of leaves and boundaries
• Visiting right boundary top-down instead of bottom-up
• Skipping root node

2. Which of the following Java method signatures is correct for a function performing boundary traversal on a binary tree node?

easy

A. public void boundaryTraversal() Node root

B. void boundaryTraversal(Node root) public

C. public boundaryTraversal(Node root) void

D. public void boundaryTraversal(Node root)

Solution

1. Step 1: Recall Java method syntax

   Java methods start with access modifier, then return type, then method name and parameters.

2. Step 2: Match correct syntax

   public void boundaryTraversal(Node root) matches: public void boundaryTraversal(Node root). Others have wrong order or missing parts.

3. Final Answer:

   public void boundaryTraversal(Node root) -> Option D

4. Quick Check:

   Access modifier + return type + method name + parameters [OK]

Hint: Java method = access modifier + return type + name + params [OK]

Common Mistakes:

• Placing return type after method name
• Missing access modifier
• Incorrect parameter placement

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

        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 boundary nodes

   Root: 1; Left boundary top-down: 2 (excluding leaf 4); Leaves left to right: 4,7,8,9; Right boundary bottom-up: 6,3 (excluding leaves).

2. Step 2: Combine nodes without duplicates

   Boundary traversal: 1 (root), 2 (left boundary), 4,7,8,9 (leaves), 6,3 (right boundary).

3. Final Answer:

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

4. Quick Check:

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

Hint: Leaves included once; right boundary reversed; avoid duplicates [OK]

Common Mistakes:

• Including leaf nodes twice
• Wrong order of right boundary nodes
• Missing leaf nodes

4. Consider this Java method snippet for boundary traversal:

void printLeftBoundary(Node node) {
  if (node == null) return;
  System.out.print(node.data + " ");
  if (node.left != null) {
    printLeftBoundary(node.left);
  } else if (node.right != null) {
    printLeftBoundary(node.right);
  }
}

What is the bug in this code?

medium

A. It prints leaf nodes which should be excluded in left boundary

B. It does not print the root node

C. It causes infinite recursion on leaf nodes

D. It prints right boundary nodes instead of left

Solution

1. Step 1: Analyze leaf node printing

   The code prints node data before checking for children, thus printing leaf nodes as well.

2. Step 2: Identify leaf node exclusion missing

   Leaf nodes should not be printed in left boundary function, but this code prints them unconditionally after null check.

3. Final Answer:

   It prints leaf nodes which should be excluded in left boundary -> Option A

4. Quick Check:

   Left boundary excludes leaves, code prints them [OK]

Hint: Exclude leaf nodes in boundary functions to avoid duplicates [OK]

Common Mistakes:

• Not checking if node is leaf before printing
• Confusing left and right boundary logic
• Missing base case for null nodes

5. You have a binary tree where some nodes have only right children, and leaves are only on the rightmost path. How should you modify the boundary traversal algorithm to correctly print the boundary without duplicates?

hard

A. Skip printing left boundary if no left child; print leaves only once; print right boundary bottom-up excluding leaves

B. Print all nodes in preorder to cover all boundaries and leaves

C. Print left boundary top-down including leaves; skip right boundary

D. Print leaves first, then left and right boundaries in any order

Solution

1. Step 1: Understand tree structure

   Since leaves are only on rightmost path and some nodes have only right children, left boundary may be missing or partial.

2. Step 2: Modify traversal rules

   Skip left boundary if no left child; print leaves once; print right boundary bottom-up excluding leaves to avoid duplicates.

3. Step 3: Combine for correct boundary

   This ensures no duplicates and correct order for such skewed trees.

4. Final Answer:

   Skip printing left boundary if no left child; print leaves only once; print right boundary bottom-up excluding leaves -> Option A

5. Quick Check:

   Handle missing left boundary and leaf duplicates carefully [OK]

Hint: Skip missing boundaries; print leaves once; reverse right boundary [OK]

Common Mistakes:

• Printing leaves multiple times
• Ignoring missing left boundary
• Printing right boundary top-down causing wrong order