Tree Traversal Inorder Left Root Right in DSA Python - Execution Trace

Concept Flow - Tree Traversal Inorder Left Root Right

Start at root node

↓

Traverse left subtree

↓

Visit current node (root)

↓

Traverse right subtree

↓

End

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

Execution Sample

DSA Python

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)

This code performs an inorder traversal of a binary tree, printing nodes in left-root-right order.

Execution Table

Step	Operation	Node Visited	Action	Tree State (Inorder so far)
1	Start traversal	A (root)	Go left subtree
2	Traverse left subtree	B	Go left subtree
3	Traverse left subtree	D	Go left subtree (None)
4	Visit node	D	Print D	D
5	Traverse right subtree	D	Go right subtree (None)	D
6	Return to parent	B	Print B	D B
7	Traverse right subtree	B	Go right subtree	D B
8	Traverse left subtree	E	Go left subtree (None)	D B
9	Visit node	E	Print E	D B E
10	Traverse right subtree	E	Go right subtree (None)	D B E
11	Return to parent	A	Print A	D B E A
12	Traverse right subtree	A	Go right subtree	D B E A
13	Traverse left subtree	C	Go left subtree	D B E A
14	Traverse left subtree	F	Go left subtree (None)	D B E A
15	Visit node	F	Print F	D B E A F
16	Traverse right subtree	F	Go right subtree (None)	D B E A F
17	Return to parent	C	Print C	D B E A F C
18	Traverse right subtree	C	Go right subtree	D B E A F C
19	Traverse left subtree	G	Go left subtree (None)	D B E A F C
20	Visit node	G	Print G	D B E A F C G
21	Traverse right subtree	G	Go right subtree (None)	D B E A F C G
22	End traversal	A	Traversal complete	D B E A F C G

💡 Traversal ends after visiting all nodes in left-root-right order.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 9	After Step 11	After Step 15	After Step 17	After Step 20	Final
Current Node	A	D	B	E	A	F	C	G	None
Inorder Output		D	D B	D B E	D B E A	D B E A F	D B E A F C	D B E A F C G	D B E A F C G

Key Moments - 3 Insights

Why do we visit the left subtree before printing the root node?

In inorder traversal, the rule is to visit left subtree first, then root, then right subtree. This is shown in execution_table rows 1-4 where we go left before printing node D.

What happens when a node has no left or right child?

When a node's left or right child is None, the traversal returns immediately without printing, as seen in steps 3, 8, 14, 19 where left or right subtree is None.

How do we know when the traversal is complete?

Traversal completes after all nodes are visited in left-root-right order, shown in step 22 where the traversal ends after printing all nodes.

Visual Quiz - 3 Questions

Look at the execution_table, what is the inorder output after step 11?

A D B E

B D B E A

C D B

D D B E A F

💡 Hint

Check the 'Tree State (Inorder so far)' column at step 11 in execution_table.

At which step does the traversal visit node F?

A Step 15

B Step 9

C Step 20

D Step 6

💡 Hint

Look for 'Visit node' action with node F in execution_table.

If node E had a left child, how would the traversal change?

A The traversal would skip E

B The traversal would visit E before its left child

C The traversal would visit that left child before E

D The traversal would visit E twice

💡 Hint

Inorder visits left subtree before root, see steps 7-9 for E.

Concept Snapshot

Inorder Tree Traversal:
- Visit left subtree first
- Then visit root node
- Finally visit right subtree
- Prints nodes in ascending order for BST
- Uses recursion or stack
- Common for sorted output

Full Transcript

Inorder traversal of a binary tree means visiting the left subtree, then the root node, and finally the right subtree. The code uses recursion to go as left as possible, then prints the node value, then goes right. The execution table shows each step visiting nodes D, B, E, A, F, C, G in that order. Variables track the current node and the output sequence growing after each print. Key moments clarify why left subtree is visited first, what happens with empty children, and when traversal ends. The visual quiz tests understanding of output at steps and effects of adding children. The snapshot summarizes the traversal rules and usage.

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