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

Tree Traversal Inorder Left Root Right

📖 Scenario: You are working with a simple family tree where each person has a left child and a right child. You want to visit each person in a specific order: first the left child, then the person themselves, and finally the right child. This order is called inorder traversal.

🎯 Goal: Build a program that creates a small binary tree, sets up a function to traverse it inorder (left, root, right), and prints the values of the nodes in that order.

📋 What You'll Learn

Create a binary tree node structure with an integer value and pointers to left and right children

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

Write a recursive function called inorderTraversal that visits nodes in left-root-right order

Print the node values during the inorder traversal separated by spaces

💡 Why This Matters

🌍 Real World

Tree traversal is used in many applications like searching files, organizing data, and parsing expressions.

💼 Career

Understanding tree traversal is essential for software developers working with data structures, databases, and algorithms.

1

Create the binary tree nodes

Create a struct called Node with an int data field and two pointers called left and right to Node. Then create three nodes called root, leftChild, and rightChild with values 1, 2, and 3 respectively. Connect root.left to leftChild and root.right to rightChild.

DSA C

# Define struct Node and create root, leftChild, rightChild nodes
# Your code here

Hint

Use a struct with int data and two pointers left and right. Initialize nodes with values and connect them by assigning pointers.

2

Add the inorder traversal function declaration

Add a function declaration for void inorderTraversal(Node* node) above main. This function will later be used to visit nodes in left-root-right order.

DSA C

#include 
#include 

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

// Declare the inorderTraversal function
// Your code here

int main() {
    Node root = {1, NULL, NULL};
    Node leftChild = {2, NULL, NULL};
    Node rightChild = {3, NULL, NULL};

    root.left = &leftChild;
    root.right = &rightChild;

    return 0;
}

Hint

Write the function prototype with return type void and parameter Node* node.

3

Implement the inorder traversal function

Implement the inorderTraversal function to recursively visit the left child, print the current node's data followed by a space, and then visit the right child. Use an if statement to check if the node is not NULL before visiting children.

DSA C

#include 
#include 

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

void inorderTraversal(Node* node) {
    // Your code here
}

int main() {
    Node root = {1, NULL, NULL};
    Node leftChild = {2, NULL, NULL};
    Node rightChild = {3, NULL, NULL};

    root.left = &leftChild;
    root.right = &rightChild;

    return 0;
}

Hint

Use recursion to visit left child, print current node, then right child. Check for NULL to stop recursion.

4

Call inorder traversal and print the output

In main, call inorderTraversal with the address of root. Then print a newline character using printf("\n") to end the output cleanly.

DSA C

#include 
#include 

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

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

int main() {
    Node root = {1, NULL, NULL};
    Node leftChild = {2, NULL, NULL};
    Node rightChild = {3, NULL, NULL};

    root.left = &leftChild;
    root.right = &rightChild;

    // Call inorderTraversal and print newline
    // Your code here
}

Hint

Call inorderTraversal(&root); and then printf("\n"); to print the traversal result and a newline.

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