Boundary Traversal of Binary Tree in DSA C - 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

DSA C

/* Boundary traversal prints nodes in this order: root, left boundary (excluding leaves), leaves, right boundary (excluding leaves) in reverse */

// Tree nodes: 1,2,3,4,5,6,7,8
// Expected output: 1 -> 2 -> 4 -> 7 -> 8 -> 6 -> 3 -> null

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

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

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

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

💡 Hint

Remember to exclude leaf nodes from left and right boundaries and include all leaves in left to right order.

Boundary traversal includes root, left boundary excluding leaves, all leaves from left to right, and right boundary excluding leaves in reverse order. Here, left boundary is 2,4 (4 is leaf so excluded), leaves are 4,7,8,6, right boundary is 3 (excluding leaf 6). So final order is 1,2,4,7,8,6,3.

🧠 Conceptual

intermediate

Understanding Leaf Nodes in Boundary Traversal

In boundary traversal of a binary tree, which of the following statements about leaf nodes is correct?

A Leaf nodes are included only if they are part of the left boundary.

B Leaf nodes are included twice if they appear in both left and right boundaries.

C Leaf nodes are excluded from the traversal entirely.

D Leaf nodes are included only once in the traversal, regardless of whether they appear in left or right boundary.

💡 Hint

Think about avoiding duplicates in the output.

Leaf nodes are included exactly once in the boundary traversal to avoid duplicates. They are collected separately after left and right boundaries are processed.

❓ Predict Output

advanced

Output of Boundary Traversal on 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 left to right, right boundary excluding leaves reversed */

// Expected output: 10 -> 20 -> 40 -> 80 -> 60 -> 90 -> 70 -> 30 -> null

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

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

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

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

💡 Hint

Check which nodes are leaves and which are boundaries carefully.

Left boundary excluding leaves: 20, 40 (40 is leaf so excluded), so only 20. Leaves: 40, 80, 60, 90. Right boundary excluding leaves: 30, 70 (70 is not leaf because it has right child 90), so 30, 70 reversed is 70, 30. Final order: 10, 20, 40, 80, 60, 90, 70, 30.

🔧 Debug

advanced

Identify the Error in Boundary Traversal Code Snippet

What error will the following C code snippet produce when performing boundary traversal on a binary tree?

Code snippet:

void printLeftBoundary(Node* root) {
    if (root == NULL) return;
    if (root->left) {
        printf("%d ", root->data);
        printLeftBoundary(root->left);
    } else if (root->right) {
        printf("%d ", root->data);
        printLeftBoundary(root->right);
    }
}

void printLeaves(Node* root) {
    if (root == NULL) return;
    printLeaves(root->left);
    if (root->left == NULL && root->right == NULL)
        printf("%d ", root->data);
    printLeaves(root->right);
}

void printRightBoundary(Node* root) {
    if (root == NULL) return;
    if (root->right) {
        printRightBoundary(root->right);
        printf("%d ", root->data);
    } else if (root->left) {
        printRightBoundary(root->left);
        printf("%d ", root->data);
    }
}

void printBoundary(Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    printLeftBoundary(root->left);
    printLeaves(root->left);
    printLeaves(root->right);
    printRightBoundary(root->right);
}

A Leaves on the left boundary are printed twice.

B Left boundary includes leaf nodes causing duplicates.

C Right boundary nodes are printed before leaves causing wrong order.

D Root node is printed twice causing duplicate output.

💡 Hint

Check if left boundary printing excludes leaf nodes.

The printLeftBoundary function prints all nodes with left or right child, but it does not exclude leaf nodes explicitly. So leaf nodes on left boundary get printed twice: once in left boundary and once in leaves.

🚀 Application

expert

Number of Nodes in Boundary Traversal

Given a binary tree with N nodes, what is the maximum number of nodes that can appear in its boundary traversal?

A N (all nodes can appear in boundary traversal)

B N - 1 (all except one node can appear)

C At most 2 * (height of tree) - 1

D At most height of tree + number of leaves

💡 Hint

Consider a skewed tree where all nodes form the boundary.

In a skewed tree (like a linked list), all nodes are boundary nodes (left boundary, leaves, and right boundary overlap). So maximum nodes in boundary traversal can be all N nodes.

Practice

1. What is the main purpose of the Boundary Traversal of Binary Tree?

easy

A. To print all nodes on the boundary of the tree in an anti-clockwise direction

B. To print all nodes in level order

C. To print all leaf nodes only

D. To print nodes in in-order traversal

Solution

1. Step 1: Understand boundary traversal definition

   Boundary traversal prints nodes on the edges of the tree: left boundary, leaves, and right boundary.

2. Step 2: Compare with other traversals

   Level order prints all nodes level-wise, leaf traversal prints only leaves, in-order prints nodes in left-root-right order.

3. Final Answer:

   To print all nodes on the boundary of the tree in an anti-clockwise direction -> Option A

4. Quick Check:

   Boundary traversal = print edges anti-clockwise [OK]

Hint: Boundary traversal prints edges anti-clockwise [OK]

Common Mistakes:

• Confusing boundary traversal with level order traversal
• Thinking it prints only leaf nodes
• Mixing it up with in-order traversal

2. Which of the following is the correct C function signature to perform boundary traversal on a binary tree node pointer named root?

easy

A. void boundaryTraversal(struct Node* root);

B. int boundaryTraversal(Node root);

C. void boundaryTraversal(Node root);

D. int boundaryTraversal(struct Node* root);

Solution

1. Step 1: Check parameter type for binary tree node

   Binary tree nodes are usually passed as pointers to struct Node in C.

2. Step 2: Check return type for traversal functions

   Traversal functions usually return void as they print nodes or store results externally.

3. Final Answer:

   void boundaryTraversal(struct Node* root); -> Option A

4. Quick Check:

   Pointer parameter + void return = void boundaryTraversal(struct Node* root); [OK]

Hint: Traversal functions usually take pointer and return void [OK]

Common Mistakes:

• Using struct keyword incorrectly
• Passing node by value instead of pointer
• Returning int instead of void

3. Consider the following binary tree:

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

What is the output of the boundary traversal (anti-clockwise) of this tree?

medium

A. [1, 2, 4, 5, 7, 8, 9, 10, 6, 3]

B. [1, 2, 4, 7, 8, 9, 10, 3, 6]

C. [1, 2, 4, 7, 8, 9, 10, 6, 3]

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

Solution

1. Step 1: Identify left boundary nodes

   Left boundary excluding leaves: 1, 2

2. Step 2: Identify leaf nodes left to right

   Leaves: 4, 7, 8, 9, 10

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

   Right boundary: 6, 3

4. Step 4: Combine in anti-clockwise order

   Boundary traversal: 1, 2, 4, 7, 8, 9, 10, 6, 3

5. Final Answer:

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

6. Quick Check:

   Left boundary + leaves + right boundary = [1, 2, 4, 7, 8, 9, 10, 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 C code snippet is intended to print the boundary traversal of a binary tree. What is the error?

void printLeftBoundary(Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    if (root->left) {
        printLeftBoundary(root->left);
    } else if (root->right) {
        printLeftBoundary(root->right);
    }
}

medium

A. It does not print the root node

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

C. It does not handle NULL root correctly

D. It prints nodes in bottom-up order instead of top-down

Solution

1. Step 1: Analyze printing condition in left boundary

   Function prints node data before recursive call, so top-down order is correct.

2. Step 2: Check if leaf nodes are excluded

   The printf is before the child checks, so leaf nodes are printed before returning.

3. Step 3: Identify error

   Leaf nodes should not be printed in left boundary function; they are printed separately in leaf traversal.

4. Final Answer:

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

5. Quick Check:

   Left boundary excludes leaves [OK]

Hint: Exclude leaf nodes in left boundary function [OK]

Common Mistakes:

• Printing leaf nodes in left or right boundary functions
• Not checking for NULL root
• Printing nodes in wrong order

5. Given a binary tree where some nodes have only one child, how should the boundary traversal be adapted to correctly include all boundary nodes without duplicates? Choose the best approach.

hard

A. Traverse all nodes in level order and print only those with one child

B. Traverse left and right boundaries including leaves, then print all leaves

C. Print all nodes in in-order traversal and remove duplicates afterwards

D. Traverse left boundary top-down excluding leaves, then all leaves left to right, then right boundary bottom-up excluding leaves, skipping duplicates

Solution

1. Step 1: Understand boundary traversal with single-child nodes

   Nodes with one child may appear in left or right boundary or as leaves.

2. Step 2: Avoid duplicates by excluding leaves in boundary traversals

   Left and right boundary traversals exclude leaves to avoid duplicates; leaves are printed separately.

3. Step 3: Combine traversals carefully

   Traverse left boundary top-down excluding leaves, then leaves left to right, then right boundary bottom-up excluding leaves, skipping duplicates.

4. Final Answer:

   Traverse left boundary top-down excluding leaves, then all leaves left to right, then right boundary bottom-up excluding leaves, skipping duplicates -> Option D

5. Quick Check:

   Exclude leaves in boundaries, print leaves separately [OK]

Hint: Exclude leaves in boundaries, print leaves separately [OK]

Common Mistakes:

• Including leaves in both boundary and leaf traversals causing duplicates
• Ignoring nodes with single child in boundary
• Printing nodes in wrong order