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 stored in a computer. You want to visit each family member starting from the oldest ancestor, then their children, and so on. This is called preorder traversal in trees.

🎯 Goal: You will build a simple program in C to create a small tree and print its nodes in preorder (root, left, right) order.

📋 What You'll Learn

Create a tree node structure with integer data and left and right child pointers

Manually create a tree with 3 nodes: root 1, left child 2, right child 3

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

Print the preorder traversal output

💡 Why This Matters

🌍 Real World

Tree traversal is used in many applications like file system navigation, expression evaluation, and organizing hierarchical data.

💼 Career

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

1

Create the tree node structure and root node

Create a struct Node with an int data and two pointers left and right. Then create a Node pointer called root and allocate memory for it. Set root->data to 1 and both root->left and root->right to NULL.

DSA C

#include 
#include 

// Define struct Node with int data and Node* left, right
// Create Node* root and allocate memory
// Set root->data = 1 and root->left = root->right = NULL
// Your code here

Hint

Use typedef struct Node to define the node. Use malloc to allocate memory for root.

2

Add left and right child nodes

Create two new nodes called leftChild and rightChild by allocating memory. Set leftChild->data to 2 and rightChild->data to 3. Set their left and right pointers to NULL. Then link them to root->left and root->right respectively.

DSA C

#include 
#include 

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

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 1;
    root->left = NULL;
    root->right = NULL;

    // Create leftChild and rightChild nodes with data 2 and 3
    // Set their left and right to NULL
    // Link leftChild to root->left and rightChild to root->right
    // Your code here

    return 0;
}

Hint

Remember to allocate memory for each child node and set their data and pointers before linking.

3

Write preorder traversal function

Write a function called preorder that takes a Node* called node. If node is not NULL, print node->data followed by a space, then recursively call preorder on node->left and node->right.

DSA C

#include 
#include 

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

void preorder(Node* node) {
    // If node is not NULL
    // Print node->data followed by space
    // Call preorder(node->left)
    // Call preorder(node->right)
    // Your code here
}

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 1;
    root->left = NULL;
    root->right = NULL;

    Node* leftChild = (Node*)malloc(sizeof(Node));
    leftChild->data = 2;
    leftChild->left = NULL;
    leftChild->right = NULL;

    Node* rightChild = (Node*)malloc(sizeof(Node));
    rightChild->data = 3;
    rightChild->left = NULL;
    rightChild->right = NULL;

    root->left = leftChild;
    root->right = rightChild;

    return 0;
}

Hint

Use a simple if check for node != NULL. Print the data then call preorder on left and right children.

4

Call preorder and print the traversal

In main, after setting up the tree, call preorder(root) to print the preorder traversal. Then print a newline using printf("\n").

DSA C

#include 
#include 

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

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

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 1;
    root->left = NULL;
    root->right = NULL;

    Node* leftChild = (Node*)malloc(sizeof(Node));
    leftChild->data = 2;
    leftChild->left = NULL;
    leftChild->right = NULL;

    Node* rightChild = (Node*)malloc(sizeof(Node));
    rightChild->data = 3;
    rightChild->left = NULL;
    rightChild->right = NULL;

    root->left = leftChild;
    root->right = rightChild;

    // Call preorder(root) and print a newline
    // Your code here

    return 0;
}

Hint

Call preorder(root) and then print a newline with printf("\n").

Practice

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

easy

A. Root, Left, Right

B. Left, Root, Right

C. Left, Right, Root

D. Right, Root, Left

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 as defined.

3. Final Answer:

   Root, Left, Right -> Option A

4. Quick Check:

   Preorder = Root, Left, Right [OK]

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

Common Mistakes:

• Confusing preorder with inorder or postorder
• Swapping left and right subtree order
• Thinking traversal starts with left child

2. Which of the following is the correct C syntax to start a preorder traversal function for a binary tree node named root?

easy

A. void preorder(Node root*) { if(root == NULL) return; ... }

B. void preorder(Node root) { if(root == NULL) return; ... }

C. void preorder(Node *root) { if(root == NULL) return; ... }

D. void preorder(Node *root) { if(root = NULL) return; ... }

Solution

1. Step 1: Check function parameter type

   Binary tree nodes are usually passed as pointers, so Node *root is correct.

2. Step 2: Check null pointer check syntax

   The condition if(root == NULL) correctly checks for null pointer. Assignment = is wrong.

3. Final Answer:

   void preorder(Node *root) { if(root == NULL) return; ... } -> Option C

4. Quick Check:

   Pointer param + null check == void preorder(Node *root) { if(root == NULL) return; ... } [OK]

Hint: Use pointer and '==' for null check in C [OK]

Common Mistakes:

• Passing node by value instead of pointer
• Using assignment '=' instead of comparison '=='
• Incorrect pointer syntax like 'Node root*'

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

    1
   / \
  2   3
 / \
4   5

medium

A. [1, 2, 4, 5, 3]

B. [4, 2, 5, 1, 3]

C. [2, 4, 5, 1, 3]

D. [1, 3, 2, 4, 5]

Solution

1. Step 1: Start at root node 1

   Preorder visits root first: 1

2. Step 2: Traverse left subtree of 1

   Visit 2, then left child 4, then right child 5: 2, 4, 5

3. Step 3: Traverse right subtree of 1

   Visit right child 3: 3

4. Final Answer:

   [1, 2, 4, 5, 3] -> Option A

5. Quick Check:

   Preorder = Root, Left, Right = [1,2,4,5,3] [OK]

Hint: Visit root, then left subtree, then right subtree [OK]

Common Mistakes:

• Mixing preorder with inorder or postorder
• Visiting children before root
• Swapping left and right subtree order

4. Identify the error in this preorder traversal function and select the fix:

void preorder(Node *root) {
  if(root == NULL) return;
  preorder(root->left);
  preorder(root->right);
  printf("%d ", root->data);
}

medium

A. Add return type 'int' instead of 'void'

B. Change 'root == NULL' to 'root = NULL' in if condition

C. Remove recursive call to right subtree

D. Move printf before recursive calls to print root first

Solution

1. Step 1: Analyze traversal order in code

   Current code prints after left and right calls, which is postorder (Left, Right, Root).

2. Step 2: Fix order to preorder

   Print root data before recursive calls to get Root, Left, Right order.

3. Final Answer:

   Move printf before recursive calls to print root first -> Option D

4. Quick Check:

   Preorder prints root before children [OK]

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

Common Mistakes:

• Printing after recursive calls (postorder)
• Using assignment '=' instead of comparison '=='
• Changing return type unnecessarily

5. You want to collect all node values in preorder traversal into an array instead of printing. Which approach correctly modifies the preorder function in C?

void preorder(Node *root, int *arr, int *index) {
  if(root == NULL) return;
  // What goes here?
}

hard

A. arr[*index] = root->data; (*index)++; preorder(root->right, arr, index); preorder(root->left, arr, index);

B. arr[(*index)++] = root->data; preorder(root->left, arr, index); preorder(root->right, arr, index);

C. preorder(root->left, arr, index); preorder(root->right, arr, index); arr[(*index)++] = root->data;

D. preorder(root->left, arr, index); arr[(*index)++] = root->data; preorder(root->right, arr, index);

Solution

1. Step 1: Understand preorder traversal order

   Preorder visits root first, so store root data before recursive calls.

2. Step 2: Correctly update array and index

   Use arr[(*index)++] = root->data; to store and increment index, then recurse left and right.

3. Final Answer:

   arr[(*index)++] = root->data; preorder(root->left, arr, index); preorder(root->right, arr, index); -> Option B

4. Quick Check:

   Store root first, then left and right [OK]

Hint: Store root data before recursive calls, increment index [OK]

Common Mistakes:

• Storing data after recursive calls (not preorder)
• Incrementing index incorrectly
• Swapping left and right recursive calls