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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Traversal on a Simple Binary Tree

What is the output of the inorder traversal (Left, Root, Right) of the following binary tree?

Tree structure:
2
/ \ 1 3

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorder(Node* root, std::vector<int>& result) {
    if (!root) return;
    inorder(root->left, result);
    result.push_back(root->val);
    inorder(root->right, result);
}

int main() {
    Node* root = new Node(2);
    root->left = new Node(1);
    root->right = new Node(3);
    std::vector<int> result;
    inorder(root, result);
    for (int v : result) std::cout << v << " ";
    return 0;
}

A [1, 2, 3]

B [2, 1, 3]

C [3, 2, 1]

D [1, 3, 2]

💡 Hint

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

Inorder traversal visits nodes in the order: left subtree, root, right subtree. For this tree, left is 1, root is 2, right is 3, so output is [1, 2, 3].

❓ Predict Output

intermediate

Inorder Traversal Output of a Larger Tree

What is the output of inorder traversal (Left, Root, Right) for this binary tree?

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

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorder(Node* root, std::vector<int>& result) {
    if (!root) return;
    inorder(root->left, result);
    result.push_back(root->val);
    inorder(root->right, result);
}

int main() {
    Node* root = new Node(4);
    root->left = new Node(2);
    root->right = new Node(5);
    root->left->left = new Node(1);
    root->left->right = new Node(3);
    std::vector<int> result;
    inorder(root, result);
    for (int v : result) std::cout << v << " ";
    return 0;
}

A [2, 1, 3, 4, 5]

B [4, 2, 1, 3, 5]

C [5, 4, 3, 2, 1]

D [1, 2, 3, 4, 5]

💡 Hint

Inorder traversal visits left subtree fully before root, then right subtree.

The inorder traversal visits nodes in order: left subtree (1,2,3), root (4), right subtree (5). So output is [1, 2, 3, 4, 5].

🔧 Debug

advanced

Identify the Error in Inorder Traversal Implementation

What error will this inorder traversal code cause when run on a non-empty tree?

DSA C++

void inorder(Node* root, std::vector<int>& result) {
    if (root == nullptr) return;
    inorder(root->right, result);
    result.push_back(root->val);
    inorder(root->left, result);
}

A The code will not compile due to syntax error

B The code will cause a segmentation fault

C The output will be reversed inorder traversal (Right, Root, Left)

D The output will be the same as correct inorder traversal

💡 Hint

Check the order of recursive calls and when the root value is added.

The code visits right subtree first, then root, then left subtree, which is reverse inorder traversal, not standard inorder.

🧠 Conceptual

advanced

Number of Nodes Visited in Inorder Traversal

Given a binary tree with 7 nodes, how many nodes will be visited during a complete inorder traversal?

A 7

B 8

C 14

D 6

💡 Hint

Inorder traversal visits every node exactly once.

Inorder traversal visits every node once, so for 7 nodes, it visits 7 nodes.

❓ Predict Output

expert

Inorder Traversal Output of Unbalanced Tree

What is the output of inorder traversal (Left, Root, Right) for this unbalanced binary tree?

Tree structure:
10
/ \ 5 15 \ \ 7 20

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorder(Node* root, std::vector<int>& result) {
    if (!root) return;
    inorder(root->left, result);
    result.push_back(root->val);
    inorder(root->right, result);
}

int main() {
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    root->left->right = new Node(7);
    root->right->right = new Node(20);
    std::vector<int> result;
    inorder(root, result);
    for (int v : result) std::cout << v << " ";
    return 0;
}

A [10, 5, 7, 15, 20]

B [5, 7, 10, 15, 20]

C [7, 5, 10, 20, 15]

D [5, 10, 7, 15, 20]

💡 Hint

Follow left subtree fully, then root, then right subtree.

Inorder traversal visits left subtree (5,7), root (10), right subtree (15,20). So output is [5, 7, 10, 15, 20].

Practice

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

easy

A. Right subtree, Root, Left subtree

B. Root, Left subtree, Right subtree

C. Left subtree, Root, Right subtree

D. Root, Right subtree, Left subtree

Solution

1. Step 1: Understand inorder traversal definition

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

2. Step 2: Apply to binary tree traversal

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

3. Final Answer:

   Left subtree, Root, Right subtree -> Option C

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 is the correct C++ function signature for inorder traversal of a binary tree node pointer Node* root?

easy

A. int inorderTraversal(Node* root)

B. int inorderTraversal(Node root)

C. void inorderTraversal(Node root)

D. void inorderTraversal(Node* root)

Solution

1. Step 1: Identify correct parameter type

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

2. Step 2: Identify correct return type

   Traversal functions typically return void because they print or process nodes without returning a value.

3. Final Answer:

   void inorderTraversal(Node* root) -> Option D

4. Quick Check:

   Pointer parameter and void return [OK]

Hint: Traversal functions use Node* and void return [OK]

Common Mistakes:

• Passing node by value instead of pointer
• Using int return type instead of void
• Missing pointer symbol * in parameter

3. Given the binary tree:

    2
   / \
  1   3

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

medium

A. 1 2 3

B. 2 1 3

C. 3 2 1

D. 1 3 2

Solution

1. Step 1: Traverse left subtree

   Start at root (2), go left to node (1), print 1 since it has no left child.

2. Step 2: Visit root and right subtree

   Return to root (2), print 2, then go right to node (3), print 3.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Inorder traversal output = 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++ inorder traversal code snippet:

void inorder(Node* root) {
  if (root == nullptr) return;
  inorder(root->left);
  std::cout << root->val << " ";
  inorder(root->right);
}

What is the error if the output is empty for a non-empty tree?

medium

A. The base case condition is incorrect

B. The function is not called with the root node

C. The print statement is missing

D. The traversal order is wrong

Solution

1. Step 1: Check base case correctness

   The base case correctly returns when root is nullptr, so no error here.

2. Step 2: Verify function call

   If output is empty, likely the function was never called with the actual root node of the tree.

3. Final Answer:

   The function is not called with the root node -> Option B

4. Quick Check:

   Missing initial call causes no output [OK]

Hint: Always call traversal with actual root node [OK]

Common Mistakes:

• Not calling traversal function at all
• Calling with nullptr instead of root
• Assuming print statement missing when it exists

5. You have a binary tree with nodes:

      4
     / \
    2   6
   / \ / \
  1  3 5  7

Using inorder traversal, which sequence of node values will you get?

hard

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

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

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

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

Solution

1. Step 1: Traverse left subtree of root (4)

   Visit left subtree rooted at 2: inorder visits 1, then 2, then 3.

2. Step 2: Visit root and right subtree

   After left subtree, visit root 4, then right subtree rooted at 6: visit 5, then 6, then 7.

3. Final Answer:

   [1, 2, 3, 4, 5, 6, 7] -> Option A

4. Quick Check:

   Inorder traversal of BST gives sorted sequence [OK]

Hint: Inorder traversal of BST returns sorted node values [OK]

Common Mistakes:

• Mixing preorder or postorder sequences
• Visiting root before left subtree
• Visiting right subtree before root