Why Boundary Traversal of Binary Tree in DSA Java?

The Big Idea

Discover how to trace the outer edge of a tree perfectly without missing a single node!

The Scenario

Imagine you have a family tree drawn on paper. You want to trace the outer edges of the tree to see all the relatives on the boundary, but you only have a pencil and no clear way to follow the edges without missing someone or going inside the tree.

The Problem

Trying to list all relatives on the boundary by checking each person manually is slow and confusing. You might miss some on the left or right edges or repeat some in the middle. It's easy to get lost and make mistakes.

The Solution

Boundary traversal of a binary tree helps you automatically walk around the tree's edges in a clear order: left boundary, leaves, then right boundary. This way, you get all the boundary nodes without repeats or misses, like tracing the family tree's outline perfectly.

Before vs After

✗ Before

void printBoundary(Node root) {
  // Manually check each node if it is on boundary
  if (root != null) {
    if (isLeftBoundary(root)) System.out.print(root.data + " ");
    printLeaves(root.left);
    printLeaves(root.right);
    if (isRightBoundary(root)) System.out.print(root.data + " ");
  }
}

✓ After

void printBoundary(Node root) {
  if (root == null) return;
  System.out.print(root.data + " ");
  printLeftBoundary(root.left);
  printLeaves(root.left);
  printLeaves(root.right);
  printRightBoundary(root.right);
}

What It Enables

This concept lets you quickly and correctly list all nodes on the outer edge of a tree, useful for visualizing or processing tree boundaries.

Real Life Example

In a map app, boundary traversal helps find the outer roads around a city area represented as a tree, so you can plan routes along the city's edges.

Key Takeaways

Manual checking of boundaries is slow and error-prone.

Boundary traversal visits left edge, leaves, and right edge in order.

It ensures all boundary nodes are included without duplicates.

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