Tree Traversal Inorder Left Root Right in DSA Java

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.

      4
     / \
    2   5
   / \
  1   3

↑ root at 4

Dry Run Walkthrough

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

Goal: Print nodes in inorder: left subtree, root, right subtree

Step 1: Start at root 4, move to left child 2

4 -> [curr->2] -> 5
2 -> 1, 3
↑ curr at 2

Why: Inorder starts with left subtree before root

Step 2: At 2, move to left child 1

4 -> 2 -> 5
2 -> [curr->1], 3
↑ curr at 1

Why: Keep going left to reach smallest node

Step 3: At 1, no left child, print 1

Print: 1
4 -> 2 -> 5
↑ curr at 1

Why: Leftmost node visited first

Step 4: Return to 2, print 2

Print: 1 2
4 -> 2 -> 5
↑ curr at 2

Why: After left subtree, visit root

Step 5: Move to right child 3, no left child, print 3

Print: 1 2 3
4 -> 2 -> 5
↑ curr at 3

Why: Visit right subtree after root

Step 6: Return to root 4, print 4

Print: 1 2 3 4
4 -> 2 -> 5
↑ curr at 4

Why: After left subtree, print root

Step 7: Move to right child 5, no left child, print 5

Print: 1 2 3 4 5
4 -> 2 -> 5
↑ curr at 5

Why: Visit right subtree last

Result:

1 2 3 4 5

Annotated Code

DSA Java

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

public class InorderTraversal {
    public static void inorder(TreeNode root) {
        if (root == null) return; // base case: no node
        inorder(root.left); // visit left subtree
        System.out.print(root.val + " "); // visit root
        inorder(root.right); // visit right subtree
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);

        inorder(root);
        System.out.println();
    }
}

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

stop recursion when no node to visit

inorder(root.left); // visit left subtree

go left first to visit smaller values

System.out.print(root.val + " "); // visit root

print current node after left subtree

inorder(root.right); // visit right subtree

go right last to visit larger values

Output

1 2 3 4 5 

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 iterative traversal, recursion is simpler but uses call stack; iterative uses explicit stack but can be more complex

Edge Cases

Empty tree (root is null)

No output, function returns immediately

DSA Java

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

Tree with single node

Prints the single node value

DSA Java

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

Tree with only left children

Prints nodes from leftmost to root in order

DSA Java

inorder(root.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: Printing the root before visiting the left subtree
Fix: Move the print statement after the recursive call to the left child

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

Summary

Visits nodes in left-root-right order to get sorted output for BSTs

Use when you want to process nodes in ascending order

The key is to first fully explore the left subtree before visiting the root

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 visits nodes in the order: left child, then root, then right child.

2. Step 2: Apply to binary tree traversal

   This means we first visit all nodes in the left subtree, then the root node, then all nodes in the right subtree.

3. Final Answer:

   Left subtree, Root, Right subtree -> Option A

4. Quick Check:

   Inorder = Left, Root, Right [OK]

Hint: Remember: Inorder means Left, Root, then 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 Java method signatures correctly represents an inorder traversal of a binary tree node named root?

easy

A. void inorderTraversal(Node root) { System.out.print(root.data); inorderTraversal(root.left); inorderTraversal(root.right); }

B. void inorderTraversal(Node root) { if(root != null) { System.out.print(root.data); inorderTraversal(root.left); inorderTraversal(root.right); } }

C. void inorderTraversal(Node root) { if(root != null) { inorderTraversal(root.right); System.out.print(root.data); inorderTraversal(root.left); } }

D. void inorderTraversal(Node root) { if(root != null) { inorderTraversal(root.left); System.out.print(root.data); inorderTraversal(root.right); } }

Solution

1. Step 1: Check the order of recursive calls

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

2. Step 2: Verify method matches inorder order

   void inorderTraversal(Node root) { if(root != null) { inorderTraversal(root.left); System.out.print(root.data); inorderTraversal(root.right); } } calls inorderTraversal on left, prints root data, then calls inorderTraversal on right, matching inorder traversal.

3. Final Answer:

   Method with left call, print root, then right call -> Option D

4. Quick Check:

   Left, Root, Right order in code [OK]

Hint: Inorder method: left call, print root, right call [OK]

Common Mistakes:

• Printing root before left subtree
• Calling right subtree before left subtree
• Missing null check before recursion

3. Given the binary tree below:

    4
   / \
  2   5
 / \
1   3

What is the output of an inorder traversal?

medium

A. 1 2 3 4 5

B. 4 2 1 3 5

C. 2 1 3 4 5

D. 1 3 2 4 5

Solution

1. Step 1: Traverse left subtree of root (4)

   Left subtree is rooted at 2, which has left child 1 and right child 3. Inorder traversal of left subtree is 1, 2, 3.

2. Step 2: Visit root and right subtree

   After left subtree, visit root 4, then right subtree 5.

3. Final Answer:

   1 2 3 4 5 -> Option A

4. Quick Check:

   Inorder visits nodes in sorted order for BST [OK]

Hint: Inorder of BST gives sorted node values [OK]

Common Mistakes:

• Visiting root before left subtree
• Mixing left and right subtree order
• Skipping leaf nodes

4. Consider this Java method for inorder traversal:

void inorder(Node root) {
  if(root == null) return;
  inorder(root.right);
  System.out.print(root.data + " ");
  inorder(root.left);
}

What is the problem with this code?

medium

A. It visits nodes in preorder instead of inorder

B. It visits nodes in postorder instead of inorder

C. It visits nodes in reverse inorder (Right, Root, Left)

D. It causes a NullPointerException

Solution

1. Step 1: Analyze the recursive call order

   The method calls inorder on right subtree first, then prints root, then calls inorder on left subtree.

2. Step 2: Compare with inorder traversal definition

   Standard inorder is Left, Root, Right. This code visits Right, Root, Left, which is reverse inorder.

3. Final Answer:

   Visits nodes in reverse inorder (Right, Root, Left) -> Option C

4. Quick Check:

   Right, Root, Left order detected [OK]

Hint: Check order of recursive calls to find traversal type [OK]

Common Mistakes:

• Assuming it is correct inorder
• Ignoring order of recursive calls
• Confusing traversal types

5. You have a binary tree where each node contains a unique integer. You want to print all node values in ascending order using inorder traversal. However, the tree is not a binary search tree (BST). Which approach ensures correct ascending order output?

hard

A. Perform inorder traversal directly and print values as visited

B. Perform inorder traversal and then sort the collected values before printing

C. Perform preorder traversal and print values as visited

D. Perform postorder traversal and print values as visited

Solution

1. Step 1: Understand inorder traversal on non-BST

   Inorder traversal visits nodes in Left, Root, Right order but does not guarantee sorted order if tree is not BST.

2. Step 2: Ensure ascending order output

   To get ascending order, collect all node values during traversal, then sort them before printing.

3. Final Answer:

   Perform inorder traversal and then sort the collected values before printing -> Option B

4. Quick Check:

   Non-BST inorder not sorted; sorting needed [OK]

Hint: Inorder only sorts BST; sort after traversal for non-BST [OK]

Common Mistakes:

• Assuming inorder traversal always sorts
• Printing values during traversal without sorting
• Using preorder or postorder expecting sorted output