Tree Traversal Inorder Left Root Right in DSA Go

Mental Model

Visit the left side first, then the middle, then the right side to see all parts in order.

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

    2
   / \
  1   3

↑ root at 2, left child 1, right child 3

Dry Run Walkthrough

Input: Tree: root 2 with left child 1 and right child 3

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

Step 1: Go to left child of root (2), which is 1

Current node: 1
Tree: 2 -> left: 1, right: 3

Why: We visit left side first in inorder traversal

Step 2: Visit node 1 (no left child)

Output: 1
Current node: 1

Why: Left child visited, now print this node

Step 3: Return to root node 2 and visit it

Output: 1 2
Current node: 2

Why: After left subtree, visit root

Step 4: Go to right child of root (2), which is 3

Current node: 3
Output: 1 2

Why: Now visit right subtree

Step 5: Visit node 3 (no children)

Output: 1 2 3
Current node: 3

Why: Right child visited last

Result:

Output: 1 2 3

Annotated Code

DSA Go

package main

import "fmt"

// Node represents a tree node
type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

// inorderTraversal prints nodes in left-root-right order
func inorderTraversal(root *Node) {
    if root == nil {
        return
    }
    inorderTraversal(root.Left) // visit left subtree
    fmt.Print(root.Val, " ") // visit root
    inorderTraversal(root.Right) // visit right subtree
}

func main() {
    // build tree: 2 with left 1 and right 3
    root := &Node{Val: 2}
    root.Left = &Node{Val: 1}
    root.Right = &Node{Val: 3}

    inorderTraversal(root)
    fmt.Println()
}

if root == nil { return }

stop recursion when no node

inorderTraversal(root.Left) // visit left subtree

go left first to reach smallest values

fmt.Print(root.Val, " ") // visit root

print current node after left subtree

inorderTraversal(root.Right) // visit right subtree

go right last to finish traversal

Output

1 2 3 

Complexity Analysis

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

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to iterative or other traversals, recursive inorder is simple but uses stack space proportional to tree height

Edge Cases

empty tree

function returns immediately without printing

DSA Go

if root == nil { return }

single node tree

prints the single node value

DSA Go

if root == nil { return }

tree with only left children

prints nodes from leftmost to root in order

DSA Go

inorderTraversal(root.Left)

When to Use This Pattern

When you need to process a binary tree in sorted order or left-root-right order, use inorder traversal because it visits nodes in ascending order for binary search trees.

Common Mistakes

Mistake: Visiting root before left subtree (preorder) instead of after
Fix: Call left subtree traversal before printing root value

Mistake: Forgetting to check for nil node and causing runtime error
Fix: Add base case to return when node is nil

Summary

It visits nodes in left subtree, then root, then right subtree order.

Use it to get nodes in sorted order from a binary search tree.

The key is to visit left side fully before the root, then right side.

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