Boundary Traversal of Binary Tree in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Boundary Traversal on a Simple Tree

What is the output of the boundary traversal for the following binary tree?

Tree structure:
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8

Boundary traversal order is: root, left boundary (excluding leaves), leaves (left to right), right boundary (excluding leaves, bottom to top).

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

        List<Integer> result = boundaryTraversal(root);
        System.out.println(result);
    }

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

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

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

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

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

A [1, 2, 4, 7, 8, 6]

B [1, 2, 4, 7, 8, 5, 6, 3]

C [1, 2, 4, 7, 8, 6, 3]

D [1, 2, 4, 5, 7, 8, 6, 3]

💡 Hint

Remember to include root, left boundary excluding leaves, all leaves left to right, then right boundary excluding leaves in reverse.

The boundary traversal starts with root (1). Left boundary excluding leaves is 2. Leaves from left to right are 4, 7, 8, 6. Right boundary excluding leaves is 3 (added bottom to top). So final order is [1, 2, 4, 7, 8, 6, 3].

🧠 Conceptual

intermediate

Understanding Boundary Traversal Components

Which of the following statements about boundary traversal of a binary tree is TRUE?

A Leaves are added only after adding left and right boundaries.

B Right boundary nodes are added in bottom to top order excluding leaf nodes.

C The left boundary includes all nodes on the left edge including leaf nodes.

D Root node is added only if it is a leaf node.

💡 Hint

Think about the order and inclusion rules for each part of the boundary.

Left boundary excludes leaf nodes to avoid duplicates with leaves. Leaves are added between left and right boundaries. Root is always added if not leaf. Right boundary is added bottom to top excluding leaves.

🔧 Debug

advanced

Identify the Bug in Boundary Traversal Code

What error or issue will occur when running this boundary traversal code snippet on a binary tree with only root node?

Code snippet:

if (!isLeaf(root)) res.add(root.data);
addLeftBoundary(root.left, res);
addLeaves(root, res);
addRightBoundary(root.right, res);

A The root node will not be added to the result list.

B The code will throw a NullPointerException when root has no children.

C Leaves will be added twice causing duplicates.

D The left boundary will include leaf nodes causing duplicates.

💡 Hint

Check the condition for adding root node when it is a leaf.

If the root is a leaf node, the condition (!isLeaf(root)) fails and root is not added. Since root is the only node, it will be missing from the result.

❓ Predict Output

advanced

Output of Boundary Traversal on a Skewed Tree

What is the output of the boundary traversal for this right skewed binary tree?

Tree structure:
1 -> 2 -> 3 -> 4 (each node has only right child)

Use the standard boundary traversal rules.

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(1);
        root.right = new Node(2);
        root.right.right = new Node(3);
        root.right.right.right = new Node(4);

        List<Integer> result = boundaryTraversal(root);
        System.out.println(result);
    }

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

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

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

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

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

A [1, 4, 3, 2]

B [1, 2, 3, 4]

C [1, 4]

D [1, 2, 3]

💡 Hint

Right boundary is added bottom to top excluding leaves; leaves are added separately.

Root is 1. Left boundary is empty (no left child). Leaves are node 4. Right boundary excluding leaves is 2 and 3 added bottom to top, so order is 1 (root), leaves (4), right boundary reversed (3, 2).

🚀 Application

expert

Count Nodes in Boundary Traversal

Given a binary tree, how many nodes will be in the boundary traversal output for the tree below?

Tree structure:
10
/ \
20 30
/ / \
40 50 60
\
70

Use standard boundary traversal rules.

A 8

B 6

C 5

D 7

💡 Hint

Count root, left boundary excluding leaves, leaves, and right boundary excluding leaves carefully without duplicates.

Root: 10 (1 node). Left boundary excluding leaves: 20 (40 is leaf). Leaves: 40, 70, 60 (3 nodes). Right boundary excluding leaves: 30, 50 (50 is not leaf because it has right child 70). Total nodes = 1 + 1 + 3 + 2 = 7.

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