Inorder Traversal

1. 1.Binary Tree Inorder Traversal
   Left -> Root -> Right: traverse left subtree, process current node, traverse right subtreeeasy
2. 2.Validate Binary Search Tree
   Inorder traversal with prev pointer: if curr.Val <= prev.Val -> return falsemedium
3. 3.Kth Smallest Element in a BST
   Inorder traversal + count: return node value when count == K (early stop!)medium
4. 4.Minimum Absolute Difference in BST
   Inorder traversal tracking prev pointer: minDiff = min(minDiff, curr.Val - prev.Val)easy
5. 5.BST Iterator
   Controlled Inorder DFS using stack: initially push all left nodes; pop & push right child left pathmedium
6. 6.Recover Binary Search Tree
   Inorder DFS detecting 1 or 2 swapped nodes where prev.Val > curr.Valmedium
7. 7.Convert BST to Greater Tree
   Reverse Inorder (Right -> Root -> Left) maintaining running summedium
8. 8.Find Mode in Binary Search Tree
   Inorder traversal tracking current count & max count without extra memoryeasy
9. 9.Two Sum IV — Input is a BST
   Inorder to sorted array + Two Pointers, or HashSet during traversaleasy
10. 10.Inorder Successor in BST
    If right subtree exists: min of right subtree. Else: last left-turn ancestormedium
11. 11.Inorder Predecessor in BST
    If left subtree exists: max of left subtree. Else: last right-turn ancestormedium
12. 12.Increasing Order Search Tree
    Inorder DFS rewiring right pointers (node.Left = nil)easy
13. 13.Binary Search Tree to Sorted List
    Inorder DFS connecting prev.Right = curr and curr.Left = prevmedium
14. 14.Balance a Binary Search Tree
    Inorder to sorted array + construct balanced BST from middlemedium
15. 15.Convert BST to Sorted Array
    Inorder DFS appending node values to sliceeasy

1. 16.Closest Binary Search Tree Value
   Binary search or Inorder tracking min abs difference to targeteasy
2. 17.Range Sum of BST
   Inorder DFS with pruning (skip Left if val < low, skip Right if val > high)easy
3. 18.Trim a Binary Search Tree
   Inorder DFS rewiring pointers for values outside [low, high] rangemedium
4. 19.Binary Tree to Doubly Linked List
   Inorder DFS connecting prev & curr pointers into circular DLLmedium
5. 20.Merge Two BSTs
   Inorder both BSTs to sorted arrays + merge two sorted arrays + rebuild BSTmedium
6. 21.Kth Largest Element in BST
   Reverse Inorder (Right -> Root -> Left) + count to Kmedium
7. 22.Recover BST with Two Swapped Nodes
   Inorder traversal finding two out-of-order nodes and swapping valueshard
8. 23.Construct BST Variants
   Inorder & Preorder combinationsmedium

How to Think

1. Need sorted values from BST?Inorder Traversal (Left -> Root -> Right)
2. Need Kth smallest?Inorder + Count to K (early stop)
3. Need compare each BST value with previous?Inorder + prev pointer
4. Need next smallest repeatedly?Controlled Inorder + Stack (BST Iterator)

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

// 1. Recursive Inorder: Left -> Root -> Right
func inorderRecursive(root *TreeNode) []int {
    result := []int{}
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        dfs(node.Left)
        result = append(result, node.Val) // Process Root in Middle!
        dfs(node.Right)
    }
    dfs(root)
    return result
}

// 2. Iterative Inorder Template: Push Left Path -> Pop & Process -> Move Right
func inorderIterative(root *TreeNode) []int {
    result := []int{}
    stack := []*TreeNode{}
    curr := root

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

        // Pop & Process
        curr = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, curr.Val)

        // Move Right
        curr = curr.Right
    }
    return result
}

The Golden Rule: BST + Inorder = Sorted Array

// Validate BST using prev Pointer
func isValidBST(root *TreeNode) bool {
    var prev *TreeNode

    var inorder func(node *TreeNode) bool
    inorder = func(node *TreeNode) bool {
        if node == nil {
            return true
        }

        if !inorder(node.Left) {
            return false
        }

        // Check if sorted order is broken!
        if prev != nil && node.Val <= prev.Val {
            return false
        }
        prev = node

        return inorder(node.Right)
    }

    return inorder(root)
}

Iterative Inorder Loop Template

// Standard Iterative Loop
for curr != nil || len(stack) > 0 {
    for curr != nil {
        stack = append(stack, curr)
        curr = curr.Left
    }
    curr = stack[len(stack)-1]
    stack = stack[:len(stack)-1]

    // process curr...

    curr = curr.Right
}

Inorder         → LEFT -> ROOT -> RIGHT (Root processed in middle)
BST + INORDER   → Strictly Sorted Array
Kth Smallest    → Count during Inorder & stop early at K
Validate BST    → Compare curr.Val against prev.Val
Iterative Loop  → Push left path -> Pop & process -> Move right

Common Interview Mistakes

Interview Rules

1. 1. Sorted values from BST needed? → Inorder Traversal
2. 2. Traversal sequence? → LEFT -> ROOT -> RIGHT
3. 3. Kth smallest in BST? → Inorder + counter early stop
4. 4. Compare adjacent BST values? → Track prev pointer during traversal
5. 5. Recover BST? → Detect sorted order violations (prev.Val > curr.Val)
6. 6. BST Iterator? → Explicit stack storing path to next smallest element
7. 7. Inorder Successor? → Smallest node in right subtree (go Right once, then Left as far as possible)
8. 8. Overall Complexity → Time: O(N) | Stack Space: O(H) (O(log N) balanced, O(N) skewed)

Inorder         → LEFT -> ROOT -> RIGHT
BST + Inorder   → SORTED
Kth Smallest    → Count inorder
Validate BST    → prev < current
Min Difference  → Compare neighbors
Recover BST     → Find broken order
Iterative Loop  → Go Left, Pop, Process, Right
Time            → O(N)

💡 Golden Rule: "Go left as far as possible, process the current node, then move right."