Tree Traversal Inorder Left Root Right in DSA C#

Mental Model

Inorder traversal visits the left child first, then the current node, and finally the right child. This order helps us see the nodes in a sorted way for binary search trees.

Analogy: Imagine reading a book where you first read the left page, then the middle page, and then the right page. This way, you don't miss anything and read in a natural order.

    2
   / \
  1   3

↑ root at 2, left child 1, right child 3

Dry Run Walkthrough

Input: Tree: root=2, left=1, right=3

Goal: Visit nodes in order: left child, root, right child to get sorted output

Step 1: Go to left child of root (2), which is 1

1 -> [curr at 1] -> null
2 -> left visited
3 -> right unvisited

Why: We start with the left subtree to follow the left-root-right order

Step 2: Visit node 1 (left child has no children)

Visited: 1
2 -> curr at root
3 -> right unvisited

Why: Left child is visited before root

Step 3: Return to root (2) and visit it

Visited: 1, 2
3 -> right unvisited

Why: After left subtree, we visit the root

Step 4: Go to right child (3) and visit it

Visited: 1, 2, 3

Why: Finally, visit the right subtree

Result:

1 -> 2 -> 3 -> null

Annotated Code

DSA C#

using System;

class Node {
    public int data;
    public Node left, right;
    public Node(int value) {
        data = value;
        left = right = null;
    }
}

class BinaryTree {
    public Node root;

    public void InorderTraversal(Node node) {
        if (node == null) return; // base case: no node

        InorderTraversal(node.left); // visit left subtree
        Console.Write(node.data + " -> "); // visit root
        InorderTraversal(node.right); // visit right subtree
    }

    static void Main() {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(2);
        tree.root.left = new Node(1);
        tree.root.right = new Node(3);

        tree.InorderTraversal(tree.root);
        Console.WriteLine("null");
    }
}

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

stop recursion when no node to visit

InorderTraversal(node.left); // visit left subtree

go left first to visit all left children

Console.Write(node.data + " -> "); // visit root

visit current node after left subtree

InorderTraversal(node.right); // visit right subtree

go right last to visit all right children

Output

1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(n) because we visit every node exactly once

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

vs Alternative: Compared to preorder or postorder, inorder is best for sorted output in binary search trees

Edge Cases

Empty tree (root is null)

Traversal does nothing and prints nothing except 'null'

DSA C#

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

Single node tree

Visits the single node and prints it followed by null

DSA C#

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

Left skewed tree (all nodes only have left child)

Visits nodes from bottom left up to root in order

DSA C#

InorderTraversal(node.left); // visit left subtree

When to Use This Pattern

When you need to visit nodes in sorted order in a binary search tree, use inorder traversal because it visits left subtree, root, then right subtree.

Common Mistakes

Mistake: Visiting root before left subtree (preorder) instead of after
Fix: Call InorderTraversal(node.left) before printing node.data

Mistake: Visiting right subtree before root
Fix: Print node.data before calling InorderTraversal(node.right)

Summary

Visits nodes in left-root-right order to get sorted output for binary search trees.

Use inorder traversal when you want to process nodes in ascending order.

The key is to first visit all left children, then the current node, then all right children.

Practice

1. What is the order of nodes visited in an inorder traversal of a binary tree?

easy

A. Left subtree, Root, Right subtree

B. Root, Left subtree, Right subtree

C. Right subtree, Root, Left subtree

D. Root, Right subtree, Left subtree

Solution

1. Step 1: Understand inorder traversal definition

   Inorder traversal means visiting the left subtree first, then the root node, and finally the right subtree.

2. Step 2: Apply the order to the tree nodes

   This order ensures nodes are visited in ascending order for binary search trees.

3. Final Answer:

   Left subtree, Root, Right subtree -> Option A

4. Quick Check:

   Inorder = Left, Root, Right [OK]

Hint: Remember: Inorder = Left, Root, Right [OK]

Common Mistakes:

• Confusing inorder with preorder or postorder
• Visiting root before left subtree
• Visiting right subtree before root

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

easy

A. void InorderTraversal(Node root)

B. int InorderTraversal(Node root)

C. Node InorderTraversal()

D. bool InorderTraversal(Node root)

Solution

1. Step 1: Identify the purpose of the method

   An inorder traversal method typically visits nodes and prints or processes them without returning a value, so it should be void.

2. Step 2: Check method signature options

   void InorderTraversal(Node root) uses void return type and accepts a Node parameter, which is correct for traversal.

3. Final Answer:

   void InorderTraversal(Node root) -> Option A

4. Quick Check:

   Traversal methods usually return void [OK]

Hint: Traversal methods usually return void [OK]

Common Mistakes:

• Using return types like int or bool unnecessarily
• Missing the root parameter
• Returning Node instead of void

3. Given the following binary tree:

    2
   / \
  1   3

What is the output of the inorder traversal method that prints node values?

medium

A. 1 3 2

B. 2 1 3

C. 3 2 1

D. 1 2 3

Solution

1. Step 1: Apply inorder traversal on the tree

   Visit left subtree (1), then root (2), then right subtree (3).

2. Step 2: Write the visited nodes in order

   The nodes are visited in order: 1, 2, 3.

3. Final Answer:

   1 2 3 -> Option D

4. Quick Check:

   Inorder traversal output = 1 2 3 [OK]

Hint: Inorder prints nodes in ascending order for BST [OK]

Common Mistakes:

• Printing root before left subtree
• Swapping left and right subtree order
• Confusing with preorder or postorder output

4. Consider this C# inorder traversal method:

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

What is the error in this code?

medium

A. It causes infinite recursion

B. It misses the base case for null root

C. It visits right subtree before left subtree, reversing inorder order

D. It does not print the root value

Solution

1. Step 1: Analyze the traversal order in the code

   The code visits root.Right first, then root, then root.Left, which is reverse of inorder.

2. Step 2: Identify the correct inorder order

   Inorder should visit left subtree first, then root, then right subtree.

3. Final Answer:

   It visits right subtree before left subtree, reversing inorder order -> Option C

4. Quick Check:

   Inorder = Left, Root, Right [OK]

Hint: Inorder must visit left subtree before right [OK]

Common Mistakes:

• Swapping left and right subtree calls
• Forgetting to check for null root
• Not printing root value

5. You have a binary tree where each node contains an integer. You want to collect all node values in a list using inorder traversal. Which C# code snippet correctly implements this?

hard

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

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

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

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

Solution

1. Step 1: Recall inorder traversal order

   Inorder visits left subtree, then root, then right subtree.

2. Step 2: Check which code matches this order

   void Inorder(Node root, List<int> result) { if (root == null) return; Inorder(root.Left, result); result.Add(root.Value); Inorder(root.Right, result); } visits left subtree, adds root value, then visits right subtree, correctly collecting values in order.

3. Final Answer:

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

4. Quick Check:

   Left, Root, Right order with result.Add(root.Value) in middle [OK]

Hint: Add root value between left and right recursive calls [OK]

Common Mistakes:

• Adding root value before left subtree
• Adding root value after right subtree
• Swapping left and right subtree calls