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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Preorder Traversal on a Simple Binary Tree

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

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

DSA C++

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

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

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->right->left = new Node(4);
    root->right->right = new Node(5);
    preorder(root);
    return 0;
}

A 1 2 4 3 5

B 1 3 4 5 2

C 1 2 3 4 5

D 2 1 4 3 5

💡 Hint

Remember preorder visits root first, then left subtree, then right subtree.

Preorder traversal visits nodes in the order: root, left subtree, right subtree. Starting at 1, then left child 2, then right subtree 3, 4, 5.

🧠 Conceptual

intermediate

Number of Nodes Visited in Preorder Traversal

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

A 8

B 6

C Depends on the tree structure

D 7

💡 Hint

Preorder traversal visits every node exactly once.

Preorder traversal visits every node in the tree exactly once, so all 7 nodes will be visited.

❓ Predict Output

advanced

Output of Preorder Traversal with Null Children

What is the output of the preorder traversal of this tree?

Tree structure:
10
/ \
null 20
/ \
30 null

DSA C++

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

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

int main() {
    Node* root = new Node(10);
    root->right = new Node(20);
    root->right->left = new Node(30);
    preorder(root);
    return 0;
}

A 10 20 30

B 10 30 20

C 20 10 30

D 10 20

💡 Hint

Preorder visits root, then left, then right. Null children are skipped.

Starting at 10, left child is null so skipped, then right child 20, then 20's left child 30.

🔧 Debug

advanced

Identify the Error in Preorder Traversal Code

What error will this preorder traversal code produce when run on a non-empty tree?

DSA C++

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

A Compilation error due to missing return type

B Prints nodes in inorder, not preorder

C Prints nodes in preorder correctly

D Runtime error due to null pointer dereference

💡 Hint

Check the order of printing and recursive calls.

The code prints left subtree first, then root, then right subtree, which is inorder traversal, not preorder.

🧠 Conceptual

expert

Preorder Traversal Output for a Skewed Tree

Consider a binary tree where every node has only a right child, forming a chain of nodes with values 1 to 5. What is the preorder traversal output?

A 2 1 3 4 5

B 1 3 5 2 4

C 1 2 3 4 5

D 5 4 3 2 1

💡 Hint

Preorder visits root first, then left (none), then right.

Since each node has only a right child, preorder visits nodes in order 1 to 5.

Practice

1. What is the order of nodes visited in a preorder tree traversal?

easy

A. Right, Root, Left

B. Left, Root, Right

C. Left, Right, Root

D. Root, Left, Right

Solution

1. Step 1: Understand preorder traversal definition

   Preorder traversal visits the root node first, then the left subtree, and finally the right subtree.

2. Step 2: Match the order with options

   Root, Left, Right matches the order Root, Left, Right exactly.

3. Final Answer:

   Root, Left, Right -> Option D

4. Quick Check:

   Preorder = Root, Left, Right [OK]

Hint: Remember preorder starts with the root node first [OK]

Common Mistakes:

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

2. Which of the following C++ function signatures correctly represents a preorder traversal of a binary tree node Node*?

easy

A. void preorder(Node* root) { if(root) { cout << root->data; preorder(root->left); preorder(root->right); } }

B. void preorder(Node* root) { if(root) { preorder(root->left); preorder(root->right); cout << root->data; } }

C. void preorder(Node* root) { if(root) { preorder(root->right); cout << root->data; preorder(root->left); } }

D. void preorder(Node* root) { if(root) { preorder(root->left); cout << root->data; preorder(root->right); } }

Solution

1. Step 1: Recall preorder traversal order

   Preorder visits root first, then left subtree, then right subtree.

2. Step 2: Check function code order

   void preorder(Node* root) { if(root) { cout << root->data; preorder(root->left); preorder(root->right); } } prints root data first, then recursively visits left and right children, matching preorder.

3. Final Answer:

   void preorder(Node* root) { if(root) { cout << root->data; preorder(root->left); preorder(root->right); } } -> Option A

4. Quick Check:

   Print root first, then left, then right [OK]

Hint: Print root data before recursive calls for preorder [OK]

Common Mistakes:

• Printing after recursive calls (postorder)
• Swapping left and right recursive calls
• Missing null check for root

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

      10
     /  \
    5    15
   /    /  \
  3    12  20

medium

A. [10, 15, 20, 12, 5, 3]

B. [10, 5, 3, 15, 12, 20]

C. [3, 5, 10, 12, 15, 20]

D. [5, 3, 10, 12, 15, 20]

Solution

1. Step 1: Start at root and visit nodes in preorder

   Visit root 10, then left subtree (5, then 3), then right subtree (15, then 12 and 20).

2. Step 2: Write traversal sequence

   Sequence is 10, 5, 3, 15, 12, 20.

3. Final Answer:

   [10, 5, 3, 15, 12, 20] -> Option B

4. Quick Check:

   Preorder = Root, Left, Right = [10,5,3,15,12,20] [OK]

Hint: Follow root, then left subtree, then right subtree order [OK]

Common Mistakes:

• Mixing preorder with inorder or postorder
• Visiting right subtree before left
• Skipping leaf nodes

4. Identify the error in the following preorder traversal function and select the corrected version:

void preorder(Node* root) {
  if(root == nullptr) return;
  preorder(root->left);
  cout << root->data << " ";
  preorder(root->right);
}

medium

A. void preorder(Node* root) { if(root == nullptr) return; cout << root->data << " "; preorder(root->left); preorder(root->right); }

B. void preorder(Node* root) { if(root == nullptr) return; preorder(root->right); cout << root->data << " "; preorder(root->left); }

C. void preorder(Node* root) { if(root == nullptr) return; preorder(root->left); preorder(root->right); cout << root->data << " "; }

D. void preorder(Node* root) { if(root == nullptr) return; cout << root->data << " "; preorder(root->right); preorder(root->left); }

Solution

1. Step 1: Identify preorder traversal order

   Preorder visits root first, then left subtree, then right subtree.

2. Step 2: Check given function and options

   The given function prints after left subtree, which is inorder traversal. void preorder(Node* root) { if(root == nullptr) return; cout << root->data << " "; preorder(root->left); preorder(root->right); } prints root first, then left, then right, matching preorder.

3. Final Answer:

   void preorder(Node* root) { if(root == nullptr) return; cout << root->data << " "; preorder(root->left); preorder(root->right); } -> Option A

4. Quick Check:

   Print root before recursive calls for preorder [OK]

Hint: Print root data before recursive calls to fix preorder [OK]

Common Mistakes:

• Printing after left subtree (inorder)
• Swapping left and right subtree calls
• Missing null pointer check

5. You have a binary tree where some nodes have only one child. How does preorder traversal help in serializing this tree uniquely, and which sequence below represents the preorder traversal of this tree?

       8
      / \
     4   10
      \    \
       6    20

hard

A. [8, 10, 20, 4, 6]

B. [4, 6, 8, 10, 20]

C. [8, 4, 6, 10, 20]

D. [6, 4, 8, 20, 10]

Solution

1. Step 1: Understand preorder traversal for serialization

   Preorder visits root first, then left subtree, then right subtree, capturing structure including nodes with single children.

2. Step 2: Traverse given tree in preorder

   Visit 8 (root), then left subtree: 4, then 6 (right child of 4), then right subtree: 10, then 20 (right child of 10).

3. Step 3: Write traversal sequence

   Sequence is [8, 4, 6, 10, 20].

4. Final Answer:

   [8, 4, 6, 10, 20] -> Option C

5. Quick Check:

   Preorder captures root-left-right including single children [OK]

Hint: Preorder captures tree shape by visiting root before children [OK]

Common Mistakes:

• Ignoring nodes with single child
• Mixing preorder with inorder
• Visiting right subtree before left