Tree Traversal Inorder Left Root Right in DSA C++ - Build from Scratch

Tree Traversal Inorder Left Root Right

📖 Scenario: Imagine you have a family tree stored in a simple tree structure. You want to visit each family member in a special order: first the left child, then the parent, then the right child. This is called inorder traversal.

🎯 Goal: You will build a small program that creates a simple tree, sets up a helper function to do inorder traversal, and then prints the nodes in the correct order.

📋 What You'll Learn

Create a simple binary tree with exactly three nodes: root with value 1, left child with value 2, right child with value 3

Create a helper function called inorderTraversal that takes a pointer to the root node and prints the values in inorder (left, root, right)

Call the inorderTraversal function with the root node

Print the values separated by spaces on one line

💡 Why This Matters

🌍 Real World

Tree traversals are used in many real-world applications like searching family trees, organizing files, and parsing expressions.

💼 Career

Understanding tree traversal is fundamental for software engineers working with data structures, databases, and algorithms.

1

Create the tree nodes

Create a struct called Node with an int data, and two pointers left and right. Then create three nodes: root with data 1, root->left with data 2, and root->right with data 3.

DSA C++

// Define struct Node and create root, root->left, root->right nodes
// Your code here

Hint

Start by defining a struct with data and two child pointers. Then create the root node and assign its left and right children.

2

Create the inorder traversal function

Write a function called inorderTraversal that takes a Node* called root. It should recursively visit the left child, print the root's data followed by a space, then visit the right child.

DSA C++

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

Node* root = new Node{1, nullptr, nullptr};
root->left = new Node{2, nullptr, nullptr};
root->right = new Node{3, nullptr, nullptr};

// Define inorderTraversal function here
// Your code here

Hint

Use recursion: first call the function on the left child, then print the current node's data, then call the function on the right child.

3

Call the inorder traversal function

Call the inorderTraversal function with the variable root to start the traversal.

DSA C++

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

Node* root = new Node{1, nullptr, nullptr};
root->left = new Node{2, nullptr, nullptr};
root->right = new Node{3, nullptr, nullptr};

void inorderTraversal(Node* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    std::cout data right);
}

// Call inorderTraversal with root
// Your code here

Hint

Simply call the function with the root node to start the traversal.

4

Print the traversal output

Add a std::cout statement to print a newline after the inorder traversal finishes.

DSA C++

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

Node* root = new Node{1, nullptr, nullptr};
root->left = new Node{2, nullptr, nullptr};
root->right = new Node{3, nullptr, nullptr};

void inorderTraversal(Node* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    std::cout data right);
}

inorderTraversal(root);
// Print a newline
// Your code here

Hint

After printing all nodes, print a newline to end the output cleanly.

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