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.