Tree Traversal Preorder Root Left Right in DSA C

Mental Model

Visit the root node first, then explore the left subtree, and finally the right subtree.

Analogy: Imagine reading a family tree starting from the oldest ancestor, then visiting their left child and all descendants, before moving to the right child and their descendants.

    1
   / \
  2   3
 / \
4   5

Dry Run Walkthrough

Input: Tree: 1 as root, 2 as left child, 3 as right child, 4 as left child of 2, 5 as right child of 2

Goal: Print nodes in preorder: root first, then left subtree, then right subtree

Step 1: Visit root node 1

Output: 1

Why: Start traversal at root

Step 2: Traverse left subtree starting at node 2

Output: 1 2

Why: After root, visit left subtree

Step 3: Traverse left subtree of node 2 starting at node 4

Output: 1 2 4

Why: Visit left child of 2 before right child

Step 4: Left and right children of 4 are null, backtrack to node 2

Output: 1 2 4

Why: No more nodes on left subtree of 4

Step 5: Traverse right subtree of node 2 starting at node 5

Output: 1 2 4 5

Why: Visit right child of 2 after left subtree

Step 6: Left and right children of 5 are null, backtrack to root 1

Output: 1 2 4 5

Why: Finished left subtree of root

Step 7: Traverse right subtree starting at node 3

Output: 1 2 4 5 3

Why: Visit right subtree after left subtree

Step 8: Left and right children of 3 are null, traversal complete

Output: 1 2 4 5 3

Why: No more nodes to visit

Result:

Output: 1 2 4 5 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define tree node structure
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Create a new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Preorder traversal: root, left, right
void preorder(Node* root) {
    if (root == NULL) return; // base case: no node
    printf("%d ", root->data); // visit root
    preorder(root->left);       // traverse left subtree
    preorder(root->right);      // traverse right subtree
}

int main() {
    // Build tree
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    // Perform preorder traversal
    preorder(root);
    printf("\n");
    return 0;
}

if (root == NULL) return;

stop traversal when no node to visit

printf("%d ", root->data);

visit current node first (root)

preorder(root->left);

traverse left subtree recursively

preorder(root->right);

traverse right subtree recursively

Output

1 2 4 5 3 

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to inorder or postorder, preorder visits nodes in a different order but same O(n) time; iterative versions may use explicit stack

Edge Cases

Empty tree (root is NULL)

Traversal ends immediately with no output

DSA C

if (root == NULL) return;

Single node tree

Only root node is printed

DSA C

if (root == NULL) return;

Tree with only left children

Nodes printed from root down left chain

DSA C

preorder(root->left);

When to Use This Pattern

When you need to process the root node before its children, use preorder traversal to visit nodes in root-left-right order.

Common Mistakes

Mistake: Visiting left or right child before the root node
Fix: Print the root node's data before recursive calls to left and right children

Summary

Visits nodes starting from root, then left subtree, then right subtree.

Use when you want to process the root before its children, such as copying a tree or prefix expression evaluation.

The key is to print or process the current node before moving to its children.

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