Boundary Traversal of Binary Tree in DSA Java - Build from Scratch

Boundary Traversal of Binary Tree

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to collect the names of family members who are on the outer edge of the tree, starting from the oldest ancestor on the left side, then all the youngest descendants at the bottom, and finally the oldest ancestors on the right side, without repeating anyone.

🎯 Goal: Build a Java program that performs a boundary traversal of a binary tree. The program will print the nodes on the boundary in the order: left boundary (top-down), leaves (left to right), and right boundary (bottom-up).

📋 What You'll Learn

Create a binary tree with specific nodes

Add helper variables or methods to assist traversal

Implement the boundary traversal logic using separate methods for left boundary, leaves, and right boundary

Print the boundary traversal result in one line separated by spaces

💡 Why This Matters

🌍 Real World

Boundary traversal helps in graphical rendering of tree edges, extracting outer elements in hierarchical data, and in certain tree-based algorithms where edge nodes are important.

💼 Career

Understanding tree traversals and boundary conditions is essential for software engineers working with data structures, especially in roles involving algorithms, system design, and coding interviews.

1

Create the Binary Tree

Create a binary tree by defining a Node class with int data, Node left, and Node right. Then create the root node with value 20, its left child with value 8, and right child with value 22. Also add left child 4 and right child 12 to node 8, and right child 25 to node 22. Finally, add left child 10 and right child 14 to node 12.

DSA Java

// Define Node class and create the binary tree with given nodes
// Your code here

Hint

Start by defining the Node class with data and pointers to left and right children. Then create the root and add children exactly as described.

2

Add Helper Methods for Boundary Traversal

Add three helper methods inside the BoundaryTraversal class: printLeftBoundary(Node node), printLeaves(Node node), and printRightBoundary(Node node). These methods will help print the left boundary (excluding leaves), all leaf nodes, and the right boundary (excluding leaves) respectively. For now, just add empty method definitions with correct signatures.

DSA Java

class Node {
    int data;
    Node left, right;

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

public class BoundaryTraversal {
    public static void main(String[] args) {
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(4);
        root.left.right = new Node(12);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        root.right.right = new Node(25);
    }

    // Add empty helper methods below
    // Your code here
}

Hint

Define the three methods with the exact names and parameters as given. Leave their bodies empty for now.

3

Implement Boundary Traversal Logic

Implement the boundary traversal inside the main method by printing the root data first, then calling printLeftBoundary(root.left), printLeaves(root.left), printLeaves(root.right), and finally printRightBoundary(root.right). Also, implement the helper methods: printLeftBoundary should print nodes on the left boundary excluding leaves, printLeaves should print all leaf nodes, and printRightBoundary should print nodes on the right boundary excluding leaves in bottom-up order. Use System.out.print(node.data + " ") to print nodes.

DSA Java

class Node {
    int data;
    Node left, right;

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

public class BoundaryTraversal {
    public static void main(String[] args) {
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(4);
        root.left.right = new Node(12);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        root.right.right = new Node(25);

        // Implement boundary traversal calls here
        // Your code here
    }

    static void printLeftBoundary(Node node) {
        // Implement left boundary traversal
        // Your code here
    }

    static void printLeaves(Node node) {
        // Implement leaf nodes printing
        // Your code here
    }

    static void printRightBoundary(Node node) {
        // Implement right boundary traversal
        // Your code here
    }
}

Hint

Print the root first. Then print the left boundary excluding leaves by going down left children. Print all leaves by checking if a node has no children. Finally, print the right boundary excluding leaves in reverse order by recursion.

4

Print the Boundary Traversal Result

Run the program to print the boundary traversal of the binary tree. The output should be the node values on the boundary separated by spaces in one line.

DSA Java

class Node {
    int data;
    Node left, right;

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

public class BoundaryTraversal {
    public static void main(String[] args) {
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(4);
        root.left.right = new Node(12);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        root.right.right = new Node(25);

        // Print the boundary traversal result
        // Your code here
    }

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

    static void printLeaves(Node node) {
        if (node == null) return;
        printLeaves(node.left);
        if (node.left == null && node.right == null) {
            System.out.print(node.data + " ");
        }
        printLeaves(node.right);
    }

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

Hint

Run the program. The output should show the boundary nodes in order separated by spaces.

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