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

Tree Traversal Preorder Root Left Right

📖 Scenario: Imagine you have a family tree and you want to visit each family member starting from the oldest ancestor, then their children from left to right.

🎯 Goal: You will build a simple binary tree and write code to visit each node in preorder: first the root, then the left child, then the right child.

📋 What You'll Learn

Create a binary tree node structure with integer values

Build a small tree with exactly 3 nodes: root, left child, and right child

Write a preorder traversal function that visits nodes in root-left-right order

Print the values of nodes as they are visited

💡 Why This Matters

🌍 Real World

Tree traversal is used in many areas like file system navigation, organizing data, and searching.

💼 Career

Understanding tree traversal is essential for software development roles involving data structures, algorithms, and system design.

1

Create the Tree Node Structure and Root Node

Create a struct called Node with an int data field and two Node* pointers called left and right. Then create a Node* variable called root and initialize it with a new Node having data = 1, and left and right set to nullptr.

DSA C++

// Your code here

Hint

Think of Node as a box holding a number and two pointers to other boxes.

2

Add Left and Right Children to the Root

Create two new Node objects with data = 2 and data = 3, both with left and right set to nullptr. Assign the node with data = 2 to root->left and the node with data = 3 to root->right.

DSA C++

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

Node* root = new Node{1, nullptr, nullptr};
// Your code here

Hint

Attach two new boxes to the left and right pointers of the root box.

3

Write the Preorder Traversal Function

Write a function called preorder that takes a Node* parameter called node. If node is not nullptr, first print node->data, then recursively call preorder on node->left, then on node->right.

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};

// Your code here

Hint

Visit the current node first, then the left child, then the right child.

4

Call Preorder and Print the Result

Call the preorder function with root as the argument. Then print a newline character using cout.

DSA C++

#include 
using namespace std;

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 preorder(Node* node) {
    if (node != nullptr) {
        cout data left);
        preorder(node->right);
    }
}

// Your code here

Hint

Call preorder(root) and print a newline after.

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