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.