Solving Binary Tree Inorder Traversal in Go: Step-by-Step Guide

Introduction to Binary Tree Inorder Traversal

Binary tree traversal is one of the foundational concepts every developer should master when learning data structures and algorithms. Among the three main depth-first traversal strategies — preorder, inorder, and postorder — inorder traversal holds a special place because of its unique property when applied to binary search trees (BSTs): it visits nodes in ascending order of their values.

In this tutorial, we will explore what inorder traversal is, why it matters, and how to implement it in Go using both recursive and iterative approaches. By the end, you will have a solid understanding of the technique and be able to apply it confidently in coding interviews and real-world applications.

What Is Inorder Traversal?

Inorder traversal is a depth-first traversal strategy that visits the nodes of a binary tree in the following order:

• Traverse the left subtree recursively.
• Visit the root node.
• Traverse the right subtree recursively.

This "Left → Root → Right" pattern ensures that for a binary search tree, the nodes are visited in sorted order. This property makes inorder traversal particularly useful for tasks like validating BSTs, finding the kth smallest element, or converting a BST into a sorted array.

Defining the Binary Tree Node in Go

Before we implement the traversal, let us define the basic structure of a binary tree node in Go:

package main

// TreeNode represents a node in a binary tree.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

This struct holds an integer value and pointers to its left and right children. With this definition in place, we can build trees and traverse them.

Why Inorder Traversal Matters

Inorder traversal is not just an academic exercise. It has several practical applications:

• Sorted output from BSTs: Inorder traversal of a BST yields nodes in ascending order, which is useful for range queries and validation.
• BST validation: By checking that the inorder traversal produces a strictly increasing sequence, you can verify whether a tree is a valid BST.
• Recovering corrupted BSTs: Problems like "Recover Binary Search Tree" rely on detecting anomalies in the inorder sequence.
• Expression tree evaluation: For expression trees, inorder traversal produces the infix notation of the expression.
• Flattening trees: Converting a BST to a sorted linked list or array often uses inorder traversal.

Understanding this traversal deeply will also help you tackle more advanced tree problems that build on the same principles.

Recursive Approach

The recursive approach is the most intuitive way to implement inorder traversal. It directly mirrors the definition: visit the left subtree, process the current node, then visit the right subtree.

Implementation

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// inorderRecursive performs an inorder traversal recursively.
func inorderRecursive(root *TreeNode) []int {
    result := []int{}
    traverse(root, &result)
    return result
}

func traverse(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    traverse(node.Left, result)
    *result = append(*result, node.Val)
    traverse(node.Right, result)
}

func main() {
    // Build the tree:
    //        1
    //         \
    //          2
    //         /
    //        3
    root := &TreeNode{Val: 1}
    root.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 3}

    fmt.Println(inorderRecursive(root)) // Output: [1 3 2]
}

How It Works

The traverse function is a helper that accepts a pointer to a slice so that we can accumulate values across recursive calls without returning slices at each level. The base case checks whether the node is nil, which means we have reached a leaf's child. Otherwise, we recurse left, append the current node's value, and then recurse right.

The time complexity is O(n) where n is the number of nodes, since each node is visited exactly once. The space complexity is O(h) where h is the height of the tree, due to the recursion stack. In the worst case of a skewed tree, this becomes O(n).

Iterative Approach

While recursion is elegant, it can cause stack overflow for very deep trees. The iterative approach simulates recursion using an explicit stack, giving you more control over memory usage and avoiding recursion limits.

Implementation

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// inorderIterative performs an inorder traversal using an explicit stack.
func inorderIterative(root *TreeNode) []int {
    result := []int{}
    stack := []*TreeNode{}
    current := root

    for current != nil || len(stack) > 0 {
        // Go as far left as possible.
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }

        // Pop the top node from the stack.
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        // Visit the node.
        result = append(result, current.Val)

        // Move to the right subtree.
        current = current.Right
    }

    return result
}

func main() {
    // Build the tree:
    //        1
    //       / \
    //      2   3
    //     / \
    //    4   5
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}

    fmt.Println(inorderIterative(root)) // Output: [4 2 5 1 3]
}

How It Works

The algorithm uses a stack to keep track of nodes as it traverses leftward. Once it can no longer go left, it pops a node from the stack, visits it, and then attempts to traverse its right subtree. This process repeats until both the current pointer is nil and the stack is empty.

The key insight is that the stack implicitly remembers the path from the root to the current node, allowing the algorithm to backtrack after reaching a leaf. The time complexity remains O(n), and the space complexity is O(h) for the stack.

Morris Traversal: O(1) Space

For scenarios where memory is constrained, Morris traversal offers an ingenious solution that performs inorder traversal with O(1) extra space. It works by temporarily modifying the tree structure, creating links from predecessor nodes back to the current node, and then restoring the tree afterward.

Implementation

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// inorderMorris performs an inorder traversal with O(1) extra space.
func inorderMorris(root *TreeNode) []int {
    result := []int{}
    current := root

    for current != nil {
        if current.Left == nil {
            // No left child, visit the current node.
            result = append(result, current.Val)
            current = current.Right
        } else {
            // Find the inorder predecessor of current.
            predecessor := current.Left
            for predecessor.Right != nil && predecessor.Right != current {
                predecessor = predecessor.Right
            }

            if predecessor.Right == nil {
                // Make current the right child of its predecessor.
                predecessor.Right = current
                current = current.Left
            } else {
                // Revert the changes made to restore the original tree.
                predecessor.Right = nil
                result = append(result, current.Val)
                current = current.Right
            }
        }
    }

    return result
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}

    fmt.Println(inorderMorris(root)) // Output: [4 2 5 1 3]
}

Morris traversal is more complex but demonstrates how tree structure can be leveraged to eliminate the need for a stack. The tree is restored to its original form by the end of the traversal, so the algorithm is non-destructive.

Best Practices

• Choose the right approach: Use recursion for clarity in most cases. Switch to the iterative approach when dealing with deep trees or when you need to avoid stack overflow.
• Pass slices by pointer: In the recursive approach, passing a pointer to the result slice avoids unnecessary allocations and copies.
• Handle edge cases: Always account for empty trees (nil root) and single-node trees in your tests.
• Test with various tree shapes: Validate your implementation against balanced trees, skewed trees, and complete trees to ensure correctness.
• Understand the trade-offs: Recursive code is easier to read but consumes stack space. Iterative code is more verbose but safer for deep trees. Morris traversal saves space but modifies the tree temporarily.
• Use traversal for validation: Remember that inorder traversal of a BST produces sorted output — a useful invariant for debugging and validation.

Common Pitfalls

• Forgetting the base case: Always check for nil before accessing node fields to avoid nil pointer dereferences.
• Mutating the tree unintentionally: Morris traversal temporarily modifies the tree. If your program is concurrent or the tree is shared, this can cause issues.
• Incorrect stack operations: In the iterative approach, make sure to pop from the stack correctly using stack[:len(stack)-1] after reading the last element.
• Confusing traversal orders: Inorder is Left-Root-Right. Mixing this up with preorder (Root-Left-Right) or postorder (Left-Right-Root) is a common mistake.

Conclusion

Inorder traversal is a fundamental technique that every Go developer working with trees should understand thoroughly. Whether you choose the simplicity of recursion, the safety of an explicit stack, or the elegance of Morris traversal, the underlying principle remains the same: visit the left subtree, process the current node, then visit the right subtree. By mastering all three approaches and understanding their trade-offs, you will be well-equipped to solve a wide range of tree-related problems in both interviews and production code. Practice implementing these solutions from scratch, test them against various tree shapes, and you will build the confidence needed to tackle even the most challenging binary tree problems.