Tree Traversal Inorder Left Root Right in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of inorder traversal?

Given the binary tree below, what is the output of an inorder traversal (Left, Root, Right)?

DSA C

/* Tree structure:
       5
      / \
     3   7
    / \   \
   2   4   8
*/

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

A 2 3 4 5 7 8

B 3 2 4 5 7 8

C 5 3 2 4 7 8

D 2 4 3 5 7 8

💡 Hint

Remember inorder traversal visits left subtree first, then root, then right subtree.

Inorder traversal visits nodes in the order: left child, root, right child. So for the given tree, the nodes are visited as 2, 3, 4, 5, 7, 8.

❓ Predict Output

intermediate

What is the inorder traversal output for this tree?

Consider the binary tree below. What will be printed by an inorder traversal?

DSA C

/* Tree structure:
       10
      /  \
     6    15
      \     \
       8     20
*/

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

A 8 6 10 15 20

B 10 6 8 15 20

C 6 10 8 15 20

D 6 8 10 15 20

💡 Hint

Inorder means left subtree first, then root, then right subtree.

The inorder traversal visits nodes in this order: 6 (left child), 8 (right child of 6), 10 (root), 15 (right child), 20 (right child of 15).

🔧 Debug

advanced

What error occurs in this inorder traversal code?

Identify the error when running this inorder traversal function on a binary tree.

DSA C

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

A Segmentation fault (accessing NULL pointer)

B No error, prints correct inorder traversal

C Compilation error due to wrong syntax

D Infinite recursion causing stack overflow

💡 Hint

Check the recursive call on the right subtree carefully.

The code calls inorderTraversal(root->right->left) instead of inorderTraversal(root->right). If root->right is NULL, accessing root->right->left causes a segmentation fault.

🧠 Conceptual

advanced

How many nodes are visited in inorder traversal of this tree?

Given the binary tree below, how many nodes will be visited during an inorder traversal?

DSA C

/* Tree structure:
       1
      / \
     2   3
    /   / \
   4   5   6
        
*/

A 5

B 4

C 6

D 7

💡 Hint

Count all nodes in the tree since inorder visits all nodes exactly once.

The tree has nodes 1,2,3,4,5,6 totaling 6 nodes. Inorder traversal visits all nodes once.

🚀 Application

expert

What is the inorder traversal output after inserting 9?

Starting from the tree below, insert node with value 9 as the right child of node 8. What is the inorder traversal output after insertion?

DSA C

/* Initial Tree:
       7
      / \
     3   10
    / \    \
   2   8    12
*/

// After insertion:
// Node 9 is right child of 8

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

A 2 3 7 8 10 9 12

B 2 3 8 9 7 10 12

C 2 3 8 7 9 10 12

D 2 3 7 8 9 10 12

💡 Hint

Remember inorder visits left subtree, root, then right subtree. The new node 9 is right child of 8.

Inorder traversal visits nodes in order: 2 (left of 3), 3, 8, 9 (right of 8), 7 (root), 10, 12.

Practice

1. What is the order of nodes visited in an inorder tree traversal?

easy

A. Left subtree, Root, Right subtree

B. Root, Left subtree, Right subtree

C. Right subtree, Root, Left subtree

D. Root, Right subtree, Left subtree

Solution

1. Step 1: Understand inorder traversal definition

   Inorder traversal visits nodes in the order: left child, root node, then right child.

2. Step 2: Apply the order to the tree

   This means we first visit all nodes in the left subtree, then the root, then all nodes in the right subtree.

3. Final Answer:

   Left subtree, Root, Right subtree -> Option A

4. Quick Check:

   Inorder = Left, Root, Right [OK]

Hint: Remember: Inorder means Left, Root, then Right [OK]

Common Mistakes:

• Confusing inorder with preorder or postorder
• Visiting root before left subtree
• Visiting right subtree before root

2. Which of the following C function prototypes correctly represents an inorder traversal of a binary tree node struct Node?

easy

A. int inorder(struct Node* root);

B. int inorder(struct Node root);

C. void inorder(struct Node root);

D. void inorder(struct Node* root);

Solution

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

   Traversal functions usually take a pointer to the root node to access the tree nodes.

2. Step 2: Check return type and parameter

   Traversal functions typically return void as they print or process nodes during traversal, so void return type with pointer parameter is correct.

3. Final Answer:

   void inorder(struct Node* root); -> Option D

4. Quick Check:

   Traversal uses pointer and void return [OK]

Hint: Traversal functions use pointer to root and void return [OK]

Common Mistakes:

• Passing struct by value instead of pointer
• Using int return type instead of void
• Missing pointer in parameter

3. Given the binary tree below:

    2
   / \
  1   3

What is the output of the inorder traversal function that prints node values?

medium

A. 2 1 3

B. 1 3 2

C. 1 2 3

D. 3 2 1

Solution

1. Step 1: Identify inorder traversal order

   Inorder visits left subtree, then root, then right subtree.

2. Step 2: Apply inorder to given tree

   Left child is 1, root is 2, right child is 3, so output is "1 2 3".

3. Final Answer:

   1 2 3 -> Option C

4. Quick Check:

   Inorder of 2-node tree = 1 2 3 [OK]

Hint: Inorder prints nodes in ascending order for BST [OK]

Common Mistakes:

• Printing root before left subtree
• Printing right subtree before root
• Confusing preorder or postorder output

4. Consider this C code snippet for inorder traversal:

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

What is the error if the function prints nodes in preorder instead of inorder?

medium

A. The printf statement is before the left subtree call

B. The base case is missing the NULL check

C. The right subtree call is missing

D. The function is missing a return type

Solution

1. Step 1: Understand traversal order in code

   Inorder prints after left subtree call and before right subtree call.

2. Step 2: Identify cause of preorder output

   If printf is before left subtree call, root prints first, causing preorder output.

3. Final Answer:

   The printf statement is before the left subtree call -> Option A

4. Quick Check:

   Print before left subtree = preorder [OK]

Hint: Print root between left and right calls for inorder [OK]

Common Mistakes:

• Placing print before left subtree call
• Omitting NULL base case
• Forgetting to call right subtree

5. You have a binary search tree with nodes inserted in this order: 5, 3, 7, 2, 4, 6, 8.
What is the inorder traversal output of this tree?

hard

A. 5 3 7 2 4 6 8

B. 2 3 4 5 6 7 8

C. 8 7 6 5 4 3 2

D. 3 2 4 5 6 7 8

Solution

1. Step 1: Build the BST structure

   Insert 5 as root, 3 left of 5, 7 right of 5, 2 left of 3, 4 right of 3, 6 left of 7, 8 right of 7.

2. Step 2: Perform inorder traversal

   Inorder visits nodes in ascending order for BST: 2, 3, 4, 5, 6, 7, 8.

3. Final Answer:

   2 3 4 5 6 7 8 -> Option B

4. Quick Check:

   Inorder of BST = sorted nodes [OK]

Hint: Inorder traversal of BST gives sorted order [OK]

Common Mistakes:

• Listing nodes in insertion order
• Reversing the order
• Skipping nodes in traversal