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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Boundary Traversal for 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

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
};

// Boundary traversal prints nodes in this order:
// root, left boundary (excluding leaves), leaves, right boundary (excluding leaves, bottom-up)

// Given the tree above, what is the printed boundary traversal sequence?

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

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

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

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

💡 Hint

Remember to exclude leaves from left and right boundaries and print leaves only once.

Boundary traversal includes root, left boundary excluding leaves, all leaves from left to right, and right boundary excluding leaves printed bottom-up. Node 5 is not part of left or right boundary but has leaves 7 and 8.

🧠 Conceptual

intermediate

Understanding Leaf Nodes in Boundary Traversal

In boundary traversal of a binary tree, which nodes are considered leaf nodes?

A Nodes on the left boundary only

B Nodes with only one child

C Nodes with no children (no left and no right child)

D Nodes on the right boundary only

💡 Hint

Think about what makes a node a leaf in any tree.

Leaf nodes are nodes that do not have any children, meaning both left and right pointers are null.

❓ Predict Output

advanced

Output of Boundary Traversal for a Complex Tree

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

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

DSA C++

/* Boundary traversal order: root, left boundary (excluding leaves), leaves, right boundary (excluding leaves, bottom-up) */

A [10, 20, 40, 70, 50, 90, 80, 60]

B [10, 20, 40, 70, 50, 80, 90, 60, 30]

C [10, 20, 40, 70, 50, 90, 80, 30, 60]

D [10, 20, 40, 70, 50, 90, 80, 60, 30]

💡 Hint

Remember to print right boundary nodes bottom-up and include all leaves from left to right.

Left boundary excluding leaves: 20, 40 (70 is leaf). Leaves: 70, 50, 90. Right boundary excluding leaves: 60, 30 printed bottom-up as 60 then 30. Root is 10.

🔧 Debug

advanced

Identify the Error in Boundary Traversal Code

Given this snippet of C++ code for printing the left boundary of a binary tree, what error will it cause?

Code:
void printLeftBoundary(Node* root) {
if (!root) return;
if (root->left) {
cout << root->data << " ";
printLeftBoundary(root->left);
} else if (root->right) {
cout << root->data << " ";
printLeftBoundary(root->right);
}
// No else to handle leaf nodes
}

A Leaves on the left boundary will not be printed at all

B Leaves on the left boundary will be printed twice

C Code will cause a segmentation fault

D Code will print right boundary nodes instead of left

💡 Hint

Check what happens when the node is a leaf (no left or right child).

The code does not print leaf nodes because it only prints when left or right child exists. Leaves are skipped here.

🚀 Application

expert

Number of Nodes in Boundary Traversal

Consider a perfect binary tree of height 3 (levels 0 to 3). How many nodes will be printed in its boundary traversal?

A 10

B 14

C 12

D 15

💡 Hint

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

A perfect binary tree of height 3 has 15 nodes. Leaves are all nodes at level 3 (8 nodes). Left boundary excluding leaves has 2 nodes, right boundary excluding leaves has 2 nodes, plus root (1). Total = 1 + 2 + 8 + 2 = 13 but root is counted once, so total 14 nodes.

Practice

1. What does the boundary traversal of a binary tree include?

easy

A. Left boundary, leaves, and right boundary nodes in order

B. Only leaf nodes from left to right

C. All nodes in level order

D. Only root and leaf nodes

Solution

1. Step 1: Understand boundary traversal components

   Boundary traversal includes the left boundary (excluding leaves), all leaf nodes, and the right boundary (excluding leaves) in reverse order.

2. Step 2: Combine all parts in order

   Traverse left boundary top-down, then leaves left to right, then right boundary bottom-up to get the full boundary traversal.

3. Final Answer:

   Left boundary, leaves, and right boundary nodes in order -> Option A

4. Quick Check:

   Boundary traversal = Left boundary + Leaves + Right boundary [OK]

Hint: Remember: left boundary + leaves + right boundary [OK]

Common Mistakes:

• Including leaf nodes twice in left or right boundary
• Ignoring right boundary order (should be bottom-up)
• Confusing boundary traversal with level order

2. Which of the following C++ function signatures is correct for printing the left boundary of a binary tree?

easy

A. void printLeftBoundary(Node* root);

B. int printLeftBoundary(Node root);

C. void printLeftBoundary(Node root);

D. int printLeftBoundary(Node* root);

Solution

1. Step 1: Identify correct parameter type for tree node

   Binary tree nodes are passed as pointers (Node*), not by value (Node), to avoid copying the entire subtree.

2. Step 2: Check return type for printing function

   Printing functions usually return void as they output directly and do not return a value.

3. Final Answer:

   void printLeftBoundary(Node* root); -> Option A

4. Quick Check:

   Pointer parameter + void return = correct signature [OK]

Hint: Use pointer parameter and void return for print functions [OK]

Common Mistakes:

• Passing node by value causing unnecessary copies
• Using int return type for printing functions
• Missing pointer symbol (*) in parameter

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

        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 left boundary nodes excluding leaves

   Left boundary: 1, 2 (4 is leaf, so excluded here)

2. Step 2: Collect all leaf nodes left to right

   Leaves: 4, 7, 8, 9

3. Step 3: Identify right boundary nodes excluding leaves in bottom-up order

   Right boundary: 6, 3

4. Step 4: Combine all parts

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

5. Final Answer:

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

6. Quick Check:

   Left boundary + leaves + right boundary = [1, 2, 4, 7, 8, 9, 6, 3] [OK]

Hint: Left boundary + leaves + right boundary in order [OK]

Common Mistakes:

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

4. The following code snippet is intended to print the right boundary of a binary tree. What is the error?

void printRightBoundary(Node* root) {
    if (!root) return;
    if (root->right) {
        printRightBoundary(root->right);
    } else if (root->left) {
        printRightBoundary(root->left);
    }
    std::cout << root->data << " ";
}

medium

A. It misses printing the root node

B. It does not print nodes in bottom-up order

C. It prints leaf nodes which should be excluded

D. It causes infinite recursion

Solution

1. Step 1: Analyze printing condition in recursion

   The function prints every node after recursive calls, including leaf nodes which should be excluded from right boundary printing.

2. Step 2: Identify missing leaf node check

   There is no check to skip printing leaf nodes, so leaf nodes get printed incorrectly as part of right boundary.

3. Final Answer:

   It prints leaf nodes which should be excluded -> Option C

4. Quick Check:

   Leaf nodes must be excluded from right boundary [OK]

Hint: Skip printing leaf nodes in boundary functions [OK]

Common Mistakes:

• Printing leaf nodes in boundary traversal
• Not checking for null nodes before recursion
• Confusing order of printing nodes

5. You want to perform boundary traversal on a binary tree that may have only one node or be skewed (all left or all right). Which approach correctly handles these edge cases?

hard

A. Print only leaf nodes as boundary in skewed trees

B. Print all nodes in level order to cover all cases

C. Print left boundary including leaves, then right boundary including leaves, ignoring root

D. Print root, then left boundary excluding leaves, then leaves, then right boundary excluding leaves, skipping duplicates

Solution

1. Step 1: Understand edge cases in boundary traversal

   Single node tree or skewed trees may cause duplicates if leaves are included in boundaries without checks.

2. Step 2: Use approach that prints root, left boundary excluding leaves, leaves, right boundary excluding leaves, and skip duplicates

   This ensures no node is printed twice and all edge cases are handled correctly.

3. Final Answer:

   Print root, then left boundary excluding leaves, then leaves, then right boundary excluding leaves, skipping duplicates -> Option D

4. Quick Check:

   Exclude leaves in boundaries + skip duplicates [OK]

Hint: Exclude leaves in boundaries and skip duplicates [OK]

Common Mistakes:

• Printing leaves twice in skewed trees
• Ignoring root node in traversal
• Using level order which is not boundary traversal