Tree Traversal Inorder Left Root Right in DSA Go - 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 nodes by first going left, then the root, then right.

Execution Sample

DSA Go

func inorder(node *Node) {
  if node == nil {
    return
  }
  inorder(node.Left)
  fmt.Print(node.Value, " ")
  inorder(node.Right)
}

This code prints tree nodes in inorder: left subtree, root, then right subtree.

Execution Table

Step	Operation	Node Visited	Left/Right	Tree State (Inorder Visited)
1	Start at root	10	root	[]
2	Traverse left subtree	5	left	[]
3	Traverse left subtree	3	left	[]
4	Traverse left subtree	nil	left	[]
5	Visit node	3	root	[3]
6	Traverse right subtree	nil	right	[3]
7	Return to parent	5	root	[3]
8	Visit node	5	root	[3,5]
9	Traverse right subtree	7	right	[3,5]
10	Traverse left subtree	nil	left	[3,5]
11	Visit node	7	root	[3,5,7]
12	Traverse right subtree	nil	right	[3,5,7]
13	Return to parent	10	root	[3,5,7]
14	Visit node	10	root	[3,5,7,10]
15	Traverse right subtree	15	right	[3,5,7,10]
16	Traverse left subtree	13	left	[3,5,7,10]
17	Traverse left subtree	nil	left	[3,5,7,10]
18	Visit node	13	root	[3,5,7,10,13]
19	Traverse right subtree	nil	right	[3,5,7,10,13]
20	Return to parent	15	root	[3,5,7,10,13]
21	Visit node	15	root	[3,5,7,10,13,15]
22	Traverse right subtree	18	right	[3,5,7,10,13,15]
23	Traverse left subtree	nil	left	[3,5,7,10,13,15]
24	Visit node	18	root	[3,5,7,10,13,15,18]
25	Traverse right subtree	nil	right	[3,5,7,10,13,15,18]
26	End	nil	none	[3,5,7,10,13,15,18]

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

Variable Tracker

Variable	Start	After Step 5	After Step 8	After Step 11	After Step 14	After Step 18	After Step 21	After Step 24	Final
Current Node	10	3	5	7	10	13	15	18	nil
Inorder Visited	[]	[3]	[3,5]	[3,5,7]	[3,5,7,10]	[3,5,7,10,13]	[3,5,7,10,13,15]	[3,5,7,10,13,15,18]	[3,5,7,10,13,15,18]

Key Moments - 3 Insights

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

Because inorder means Left-Root-Right, so we must first go all the way left before visiting the root node, as shown in steps 2-5 in the execution_table.

What happens when the node is nil?

The function returns immediately without action, stopping traversal down that path, as seen in steps 4, 6, 10, 12, 17, 19, 23, 25.

Why do we return to the parent node after finishing left and right subtrees?

Because inorder traversal visits nodes in left-root-right order, after finishing left and right children, we return to the parent to continue traversal, shown in steps 7 and 13.

Visual Quiz - 3 Questions

Look at the execution_table, what is the inorder visited list after step 14?

A [3,5,7]

B [3,5,7,10]

C [3,5]

D [3,5,7,10,13]

💡 Hint

Check the 'Tree State (Inorder Visited)' column at step 14 in execution_table.

At which step does the traversal visit node 13?

A Step 18

B Step 16

C Step 20

D Step 21

💡 Hint

Look for 'Visit node' operation with node 13 in execution_table.

If the left child of node 5 was nil, how would the inorder visited list change after step 8?

A [5,7]

B [3,5]

C [5]

D [3,7]

💡 Hint

Without left child of 5, node 3 is never visited, so after visiting 5, list is just [5].

Concept Snapshot

Inorder Tree Traversal:
- Visit left subtree first
- Then visit root node
- Then visit right subtree
- Recursive approach: call inorder(left), print root, call inorder(right)
- Result: nodes visited in ascending order for BST

Full Transcript

Inorder traversal means visiting the left subtree, then the root node, then the right subtree. The code recursively calls itself on the left child until it reaches nil, then visits the node, then calls itself on the right child. The execution table shows each step visiting nodes 3, 5, 7, 10, 13, 15, and 18 in order. Variables track the current node and the list of visited nodes. Key moments clarify why nodes are visited after left subtree and what happens when nodes are nil. The quiz tests understanding of the visited order and traversal steps.

Practice

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

easy

A. Root node, Right subtree, Left subtree

B. Root node, Left subtree, Right subtree

C. Right subtree, Root node, Left subtree

D. Left subtree, Root node, Right 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 traversal order

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

3. Final Answer:

   Left subtree, Root node, Right subtree -> Option D

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 Go function signatures correctly represents an inorder traversal function for a binary tree node defined as type Node struct { Val int; Left, Right *Node }?

easy

A. func inorder(root *Node) []int

B. func inorder(root Node) []int

C. func inorder(root *Node) int

D. func inorder(root Node) int

Solution

1. Step 1: Understand pointer usage in Go for trees

   Binary trees use pointers to nodes to allow recursive traversal and modification.

2. Step 2: Choose function signature returning slice of ints

   Inorder traversal returns a list of node values, so return type should be []int, and input should be pointer to Node.

3. Final Answer:

   func inorder(root *Node) []int -> Option A

4. Quick Check:

   Pointer receiver and slice return type [OK]

Hint: Use pointer receiver and return slice for traversal [OK]

Common Mistakes:

• Passing Node by value instead of pointer
• Returning single int instead of slice
• Using incorrect return type

3. What is the output of the inorder traversal for the following binary tree?

    2
   / \
  1   3

Given the Go code:

type Node struct {
    Val int
    Left, Right *Node
}

func inorder(root *Node) []int {
    if root == nil {
        return []int{}
    }
    left := inorder(root.Left)
    right := inorder(root.Right)
    return append(append(left, root.Val), right...)
}

func main() {
    root := &Node{2, &Node{1, nil, nil}, &Node{3, nil, nil}}
    result := inorder(root)
    fmt.Println(result)
}

medium

A. [3, 2, 1]

B. [2, 1, 3]

C. [1, 2, 3]

D. [1, 3, 2]

Solution

1. Step 1: Trace inorder traversal on given tree

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

2. Step 2: Confirm output list order

   The traversal returns [1, 2, 3] as expected for inorder.

3. Final Answer:

   [1, 2, 3] -> Option C

4. Quick Check:

   Inorder traversal output = [1, 2, 3] [OK]

Hint: Inorder visits left, root, then right [OK]

Common Mistakes:

• Appending root before left subtree
• Appending right subtree before root
• Confusing preorder or postorder output

4. The following Go code attempts inorder traversal but produces incorrect output. What is the bug?

func inorder(root *Node) []int {
    if root == nil {
        return []int{}
    }
    left := inorder(root.Left)
    right := inorder(root.Right)
    return append(left, right...)
    return append(result, root.Val)
}

medium

A. The root value is appended after the return statement, so never executed

B. The function should return int, not []int

C. The base case should return nil, not empty slice

D. The left subtree is not traversed

Solution

1. Step 1: Analyze return statements in function

   The first return statement returns append(left, right...), so the second return is unreachable.

2. Step 2: Identify missing root value append

   Root value is never appended because code after first return is ignored.

3. Final Answer:

   The root value is appended after the return statement, so never executed -> Option A

4. Quick Check:

   Code after return is unreachable [OK]

Hint: Check for unreachable code after return [OK]

Common Mistakes:

• Ignoring unreachable code after return
• Not appending root value in correct order
• Confusing base case return value

5. Given a binary tree where some nodes have only one child, how does inorder traversal help in printing the nodes in sorted order if the tree is a binary search tree? Consider the tree:

      5
     / \
    3   8
     \   \
      4   10

What is the inorder traversal output?

hard

A. [5, 3, 4, 8, 10]

B. [3, 4, 5, 8, 10]

C. [4, 3, 5, 10, 8]

D. [3, 5, 4, 8, 10]

Solution

1. Step 1: Apply inorder traversal on given tree

   Visit left subtree: node 3, then its right child 4, then root 5, then right subtree nodes 8 and 10.

2. Step 2: List nodes in inorder sequence

   Sequence is 3, 4, 5, 8, 10 which is sorted ascending order.

3. Final Answer:

   [3, 4, 5, 8, 10] -> Option B

4. Quick Check:

   Inorder traversal of BST gives sorted nodes [OK]

Hint: Inorder traversal of BST prints nodes sorted [OK]

Common Mistakes:

• Ignoring nodes with single child
• Visiting root before left subtree
• Mixing preorder or postorder with inorder