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. This order helps you see the tree starting from the top and going down each branch before moving sideways.

Analogy: Imagine reading a family tree starting from the oldest ancestor (root), then looking at their oldest child (left), and then the younger child (right), going down each branch fully before moving to the next sibling.

    1
   / \
  2   3
 / \   \
4   5   6
↑ Root

Dry Run Walkthrough

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

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

Step 1: Visit root node 1

Visited: 1

Why: Start traversal at the root node

Step 2: Traverse left subtree starting at node 2

Visited: 1 -> 2

Why: After root, explore left subtree fully

Step 3: Visit left child of 2: node 4

Visited: 1 -> 2 -> 4

Why: Preorder visits root of subtree before children

Step 4: Back to node 2, visit right child 5

Visited: 1 -> 2 -> 4 -> 5

Why: After left child, visit right child in left subtree

Step 5: Back to root 1, traverse right subtree starting at node 3

Visited: 1 -> 2 -> 4 -> 5 -> 3

Why: After left subtree, explore right subtree

Step 6: Visit right child of 3: node 6

Visited: 1 -> 2 -> 4 -> 5 -> 3 -> 6

Why: Visit right subtree nodes in preorder

Result:

Visited nodes in order: 1 -> 2 -> 4 -> 5 -> 3 -> 6

Annotated Code

DSA C#

using System;

class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val=0) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class Program {
    static void PreorderTraversal(TreeNode root) {
        if (root == null) return; // base case: no node
        Console.Write(root.val + " "); // visit root first
        PreorderTraversal(root.left); // then left subtree
        PreorderTraversal(root.right); // then right subtree
    }

    static void Main() {
        // Build tree from dry run input
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        PreorderTraversal(root);
        Console.WriteLine();
    }
}

if (root == null) return; // base case: no node

stop recursion when no node to visit

Console.Write(root.val + " "); // visit root first

visit current node before children

PreorderTraversal(root.left); // then left subtree

recursively traverse left subtree

PreorderTraversal(root.right); // then right subtree

recursively traverse right subtree

Output

1 2 4 5 3 6 

Complexity Analysis

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

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

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

Edge Cases

Empty tree (root is null)

No output, traversal ends immediately

DSA C#

if (root == null) return; // base case: no node

Tree with single node

Only root node is printed

DSA C#

if (root == null) return; // base case: no node

Tree with only left children

Nodes are visited top to bottom along left side

DSA C#

PreorderTraversal(root.left); // then left subtree

When to Use This Pattern

When you need to process or print a tree starting from the root and then explore each branch fully before moving sideways, use preorder traversal because it visits root before children.

Common Mistakes

Mistake: Visiting left or right child before the root node
Fix: Always print or process the root node first before recursive calls

Mistake: Forgetting to check for null nodes before recursion
Fix: Add base case to return immediately if node is null

Summary

Visits the root node first, then recursively visits left and right subtrees in order.

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

The key insight is to handle the current node before diving into its children.

Practice

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

easy

A. Left, Root, Right

B. Right, Left, Root

C. Left, Right, Root

D. Root, Left, Right

Solution

1. Step 1: Understand preorder traversal definition

   Preorder traversal visits the root node first, then recursively visits the left subtree, followed by the right subtree.

2. Step 2: Confirm the visiting order

   The visiting order is Root, then Left subtree, then Right subtree.

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 subtree before root
• Visiting right subtree before left

2. Which of the following C# method signatures correctly represents a preorder traversal method for a binary tree node class named Node?

easy

A. void PreorderTraversal(Node root)

B. int PreorderTraversal(Node root)

C. Node PreorderTraversal()

D. void PreorderTraversal()

Solution

1. Step 1: Identify typical preorder traversal method signature

   Preorder traversal usually processes nodes and does not return a value, so it returns void and takes the root node as parameter.

2. Step 2: Match method signature options

   void PreorderTraversal(Node root) matches void return type and takes Node root parameter, which is correct.

3. Final Answer:

   void PreorderTraversal(Node root) -> Option A

4. Quick Check:

   Traversal method usually void with root parameter [OK]

Hint: Traversal methods usually return void and take root node [OK]

Common Mistakes:

• Using return type int instead of void
• Not passing root node as parameter
• Using method without parameters

3. Given the following binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of a preorder traversal printing node values?

medium

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

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

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

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

Solution

1. Step 1: Start preorder traversal at root node 1

   Visit root 1 first.

2. Step 2: Traverse left subtree of 1

   Visit node 2, then its left child 4, then right child 5.

3. Step 3: Traverse right subtree of 1

   Visit node 3.

4. Final Answer:

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

5. Quick Check:

   Preorder visits root, left subtree, right subtree [OK]

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

Common Mistakes:

• Mixing preorder with inorder or postorder output
• Visiting left subtree after right subtree
• Skipping leaf nodes

4. Consider this C# preorder traversal method:

void Preorder(Node root) {
  if (root == null) return;
  Preorder(root.Left);
  Console.Write(root.Value + " ");
  Preorder(root.Right);
}

What is the error in this code?

medium

A. It visits right subtree before left subtree

B. It visits left subtree before root, so not preorder

C. It does not check for null root

D. It prints node values incorrectly

Solution

1. Step 1: Analyze the visiting order in the method

   The method calls Preorder on left child first, then prints root value, then calls Preorder on right child.

2. Step 2: Compare with preorder definition

   Preorder requires visiting root first, then left, then right. This code visits left subtree before root, so it is actually inorder traversal.

3. Final Answer:

   It visits left subtree before root, so not preorder -> Option B

4. Quick Check:

   Preorder must print root before children [OK]

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

Common Mistakes:

• Printing after left subtree call instead of before
• Confusing preorder with inorder traversal
• Missing null check (though present here)

5. You want to collect all node values of a binary tree in preorder traversal into a list in C#. Which code snippet correctly does this?

hard

A. void Preorder(Node root, List<int> result) {
if (root == null) return;
result.Add(root.Value);
Preorder(root.Left, result);
Preorder(root.Right, result);
}

B. void Preorder(Node root, List<int> result) {
if (root == null) return;
Preorder(root.Left, result);
result.Add(root.Value);
Preorder(root.Right, result);
}

C. void Preorder(Node root, List<int> result) {
if (root == null) return;
Preorder(root.Left, result);
Preorder(root.Right, result);
result.Add(root.Value);
}

D. void Preorder(Node root, List<int> result) {
if (root == null) return;
Preorder(root.Right, result);
result.Add(root.Value);
Preorder(root.Left, result);
}

Solution

1. Step 1: Understand preorder traversal collection

   Preorder means visit root first, so add root value to list before recursive calls.

2. Step 2: Check order of recursive calls

   After adding root, recursively traverse left subtree, then right subtree.

3. Final Answer:

   Code snippet that adds root value first, then left, then right -> Option A

4. Quick Check:

   Preorder = Add root, then left, then right [OK]

Hint: Add root value before recursive calls for preorder list [OK]

Common Mistakes:

• Adding node value after left subtree call (inorder)
• Adding node value after both subtree calls (postorder)
• Swapping left and right subtree calls