Tree Traversal Inorder Left Root Right in DSA Python

Mental Model

Visit the left side first, then the middle, then the right side in order.

Analogy: Imagine reading a book where you first look at the left page, then the center page, then the right page in order.

    1
   / \
  2   3
 / 
4  

↑ start at root (1)

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2, right child 3, and 2 has left child 4

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

Step 1: Go left from 1 to 2

1 -> [curr->2] -> 3
2 -> [curr->4]
4
3

Why: We visit left subtree first

Step 2: Go left from 2 to 4

1 -> 2 -> [curr->4] -> 3
4

Why: Keep going left until no more left child

Step 3: Visit 4 (no left child)

Visited: 4
1 -> 2 -> 3

Why: Leftmost node visited first

Step 4: Go back to 2 and visit it

Visited: 4, 2
1 -> 3

Why: After left subtree, visit root

Step 5: No right child of 2, go back to 1 and visit it

Visited: 4, 2, 1
3

Why: After root, visit right subtree

Step 6: Go right from 1 to 3 and visit it

Visited: 4, 2, 1, 3

Why: Visit right subtree last

Result:

4 -> 2 -> 1 -> 3

Annotated Code

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def inorder_traversal(root):
    result = []
    def helper(node):
        if node is None:
            return
        helper(node.left)  # visit left subtree first
        result.append(node.val)  # then visit root
        helper(node.right)  # finally visit right subtree
    helper(root)
    return result

# Build tree from dry_run input
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)

output = inorder_traversal(root)
print(' -> '.join(map(str, output)))

helper(node.left) # visit left subtree first

advance to left child to visit all left nodes first

result.append(node.val) # then visit root

add current node value after left subtree is done

helper(node.right) # finally visit right subtree

visit right subtree after root

Output

4 -> 2 -> 1 -> 3

Complexity Analysis

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

Space: O(n) due to recursion stack in worst case (skewed tree) and output list

vs Alternative: Compared to iterative traversal, recursive is simpler but uses call stack; iterative uses explicit stack but same time complexity

Edge Cases

Empty tree (root is None)

Returns empty list without error

DSA Python

if node is None:
            return

Single node tree

Returns list with single node value

DSA Python

if node is None:
            return

Tree with only left children

Visits nodes from leftmost up to root in order

DSA Python

helper(node.left)  # visit left subtree first

When to Use This Pattern

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

Common Mistakes

Mistake: Visiting root before left subtree
Fix: Change order to visit left subtree first, then root

Mistake: Forgetting to visit right subtree
Fix: Add recursive call to right child after visiting root

Summary

Visits nodes in left-root-right order

Use when you want nodes in sorted order from a binary search tree

The key is to visit left subtree fully before root, then right subtree

Practice

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

easy

A. Root, Left subtree, Right subtree

B. Root, Right subtree, Left subtree

C. Right subtree, Root, Left subtree

D. Left subtree, Root, Right subtree

Solution

1. Step 1: Understand inorder traversal definition

   Inorder traversal visits nodes in the order: left subtree first, then root node, then right subtree.

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

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

3. Final Answer:

   Left subtree, Root, Right subtree -> Option D

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 Python function definitions correctly implements inorder traversal of a binary tree node root?

easy

A. def inorder(root):
if root:
inorder(root.left)
print(root.val)
inorder(root.right)

B. def inorder(root):
if root:
print(root.val)
inorder(root.left)
inorder(root.right)

C. def inorder(root):
if root:
inorder(root.right)
print(root.val)
inorder(root.left)

D. def inorder(root):
if root:
inorder(root.right)
inorder(root.left)
print(root.val)

Solution

1. Step 1: Recall inorder traversal order

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

2. Step 2: Match code to order

   def inorder(root): if root: inorder(root.left) print(root.val) inorder(root.right) calls inorder on left, prints root value, then calls inorder on right, matching inorder traversal.

3. Final Answer:

   Option A code correctly implements inorder traversal -> Option A

4. Quick Check:

   Left, Root, Right order in code [OK]

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

Common Mistakes:

• Printing root before left subtree call
• Swapping left and right subtree calls
• Missing base case check for None

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

    2
   / \
  1   3

class Node: def __init__(self, val): self.val = val self.left = None self.right = None def inorder(root): if root: inorder(root.left) print(root.val, end=' ') inorder(root.right) root = Node(2) root.left = Node(1) root.right = Node(3) inorder(root)

medium

A. 1 2 3

B. 2 1 3

C. 3 2 1

D. 1 3 2

Solution

1. Step 1: Trace inorder traversal on given tree

   Start at root (2), first visit left subtree (1), print 1, then print root 2, then visit right subtree (3), print 3.

2. Step 2: Write output sequence

   The printed sequence is: 1 2 3.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Inorder 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 outputs
• Confusing preorder or postorder output

4. The following code is intended to perform inorder traversal but produces no output. What is the error?

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def inorder(root):
    inorder(root.left)
    print(root.val, end=' ')
    inorder(root.right)

root = Node(1)
inorder(root)

medium

A. The root node is never created

B. The print statement is outside the function

C. The base case is missing; should check if root is None first

D. The function calls right subtree before printing root

Solution

1. Step 1: Analyze base case in inorder function

   The function checks root.left and root.right but never checks if root itself is None, which causes errors or no output if root is None.

2. Step 2: Identify missing base case effect

   Without checking if root is None, the function may fail or skip printing when called with None, so adding if root is None: return fixes it.

3. Final Answer:

   The base case is missing; should check if root is None first -> Option C

4. Quick Check:

   Check root None before recursion [OK]

Hint: Always check if node is None before recursion [OK]

Common Mistakes:

• Not checking if root is None before accessing attributes
• Incorrect order of print and recursive calls
• Forgetting to create root node before traversal

5. You have a binary tree where some nodes have only one child. Which inorder traversal output correctly represents the tree below?

      5
     / \
    3   8
     \    \
      4    9

Options: A) 3 5 4 8 9 B) 4 3 5 9 8 C) 3 4 5 8 9 D) 5 3 4 8 9

hard

A. 3 5 4 8 9

B. 3 4 5 8 9

C. 4 3 5 9 8

D. 5 3 4 8 9

Solution

1. Step 1: Perform inorder traversal on given tree

   Start at root (5), visit left subtree: node 3 has no left child, so print 3, then visit right child 4, print 4. Then print root 5. Then visit right subtree: node 8 has no left child, print 8, then right child 9, print 9.

2. Step 2: Write the output sequence

   The output is: 3 4 5 8 9.

3. Final Answer:

   3 4 5 8 9 -> Option B

4. Quick Check:

   Inorder visits left, root, right even if child missing [OK]

Hint: Inorder visits left subtree fully before root, even if missing nodes [OK]

Common Mistakes:

• Skipping nodes with only one child
• Printing root before left subtree
• Confusing preorder or postorder output