Tree Traversal Inorder Left Root Right in DSA Java - 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 Java

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

This code prints the nodes of a binary tree in inorder sequence: left child, root, right child.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Visual)
1	Start at root	10	current = root(10)	10 / \ 5 15
2	Traverse left subtree	5	current = 5	10 / \ 5 15
3	Traverse left subtree	null	current = null (left of 5)	10 / \ 5 15
4	Return from null	null	back to 5	10 / \ 5 15
5	Visit node	5	print 5	10 / \ 5 15
6	Traverse right subtree	null	current = null (right of 5)	10 / \ 5 15
7	Return from null	null	back to 10	10 / \ 5 15
8	Visit node	10	print 10	10 / \ 5 15
9	Traverse right subtree	15	current = 15	10 / \ 5 15
10	Traverse left subtree	null	current = null (left of 15)	10 / \ 5 15
11	Return from null	null	back to 15	10 / \ 5 15
12	Visit node	15	print 15	10 / \ 5 15
13	Traverse right subtree	null	current = null (right of 15)	10 / \ 5 15
14	Return from null	null	back to root, traversal done	10 / \ 5 15

💡 Traversal ends after visiting all nodes: 5, 10, 15 in inorder sequence.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 12	Final
current	root(10)	5	5	10	15	null
printed_nodes	[]	[]	[5]	[5,10]	[5,10,15]	[5,10,15]

Key Moments - 3 Insights

Why do we visit the node only after traversing its left subtree?

In inorder traversal, the left subtree is visited first to ensure nodes are processed in ascending order. See execution_table steps 2-5 where left subtree nodes are visited before the root.

What happens when the current node is null?

When current is null, it means we've reached a leaf's child. We return immediately without printing. This is shown in steps 3, 6, 10, 13 where traversal returns from null nodes.

Why do we traverse the right subtree after visiting the root?

After visiting the root, inorder traversal moves to the right subtree to continue the ascending order. See steps 8-14 where after printing 10, traversal moves to right child 15.

Visual Quiz - 3 Questions

Look at the execution_table, what node is visited at step 5?

A Node 15

B Node 10

C Node 5

D Null

💡 Hint

Check the 'Node Visited' column at step 5 in the execution_table.

At which step does the traversal print the root node 10?

A Step 8

B Step 5

C Step 12

D Step 14

💡 Hint

Look for 'print 10' in the 'Pointer Changes' column in execution_table.

If the left subtree of node 5 was not null, how would the execution_table change?

A Node 5 would be visited before its left subtree

B More steps before visiting node 5

C Fewer steps overall

D Traversal would skip node 10

💡 Hint

Think about inorder traversal order and how left subtree nodes are visited before the root.

Concept Snapshot

Inorder Tree Traversal (Left, Root, Right):
- Visit left subtree recursively
- Visit current node (print data)
- Visit right subtree recursively
- Produces nodes in ascending order for BST
- Base case: node == null returns immediately

Full Transcript

Inorder traversal visits nodes in the order: left child, root, right child. Starting at the root, it recursively visits the left subtree until it reaches a null node, then prints the current node's data, and finally traverses the right subtree. This ensures nodes are printed in ascending order for binary search trees. The traversal stops when all nodes have been visited. The execution table shows each step, including visiting nodes and returning from null children. The variable tracker shows how the current node pointer moves and which nodes have been printed at each step.

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