TreeEasyO(n) time · O(n) space

Inorder Traversal

Mahabharata — The Throne Succession — Left Branch, Then Root, Then Right Branch

बायां — फिर मूल — फिर दायां। Inorder में BST — क्रमबद्ध सूची देता है॥

*Left — then root — then right. Inorder of BST — gives a sorted list.*

The Story

Perform inorder traversal (Left → Root → Right) of a binary tree.

For tree `[1,null,2,3]` (root=1, right=2, left=3): Inorder = [1,3,2]

For BST `[4,2,6,1,3,5,7]`: Inorder = [1,2,3,4,5,6,7] (sorted!)

**Recursive approach:** ```java void inorder(TreeNode root, List<Integer> res) { if (root == null) return; inorder(root.left, res); // Left res.add(root.val); // Root inorder(root.right, res); // Right } ```

**Iterative approach (Morris / Stack):** ```java Deque<TreeNode> st = new ArrayDeque<>(); while (root != null || !st.isEmpty()) { while (root != null) { st.push(root); root = root.left; } // Go left root = st.pop(); res.add(root.val); // Visit root = root.right; // Go right } ```

The iterative uses an explicit stack to simulate the call stack.

**The three DFS traversals:** - Inorder (LNR): Left, Node, Right → Sorted order for BST - Preorder (NLR): Node, Left, Right → Copy tree / serialize - Postorder (LRN): Left, Right, Node → Delete tree / evaluate expression

For BST validation, kth smallest, or sorted output: use inorder.

The Level-Order Collection

BFS collects all nodes, then sort. Not traversal. O(n log n).

java

// Inorder IS the standard. No simpler brute force.
// The recursive solution is already optimal O(n).

The Left-Root-Right Recursive/Iterative Wisdom

Recursive: inorder(left), add root, inorder(right). Iterative: push all left nodes, pop, visit, move right.

java

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> st = new ArrayDeque<>();
    while (root != null || !st.isEmpty()) {
        while (root != null) { st.push(root); root = root.left; }  // Go deep left
        root = st.pop();
        res.add(root.val);     // Visit
        root = root.right;     // Go right
    }
    return res;
}

Step-by-Step Walkthrough

Tree=[1,null,2] (root=1, right=2)
Push 1. Stack=[1]. root=1.left=null. Pop 1, add 1, root=1.right=2.
Push 2. Stack=[2]. root=2.left=null. Pop 2, add 2, root=2.right=null.
Result=[1,2] ✅

Deep Insight

**Why inorder of BST = sorted:** BST property: all left subtree values < root < all right subtree values. Inorder visits left first (smaller), then root (middle), then right (larger) → naturally sorted.

**Morris traversal O(1) space:** Modify tree structure temporarily (threaded BST). Visit left subtree's rightmost node's right pointer to create a thread back. Restores tree after. O(n) time, O(1) space — impressive but complex.

**Iterative pattern for DFS:** The iterative inorder pattern (push left chain, pop+visit, go right) is the fundamental pattern for all tree iterative DFS traversals.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n)	O(n)	Recursive call stack
Optimal	O(n)	O(n)	Iterative stack — same space but avoids recursion overhead

Pattern Recognition

✅ Inorder = Left, Root, Right
✅ BST inorder → sorted sequence
✅ Iterative: push left chain, pop+visit, go right
✅ Morris traversal = O(1) space

**LeetCode Trigger Phrases:**
→ "inorder traversal"
→ BST sorted output / kth smallest
→ Validate BST using inorder

Bhagavad Gita 10.26

अश्वत्थः सर्ववृक्षाणां देवर्षीणां च नारदः। गन्धर्वाणां चित्ररथः सिद्धानां कपिलो मुनिः॥

Among trees I am the Ashvattha; among divine sages Narada; among Gandharvas, Chitraratha; among the perfected, the sage Kapila.

Connection: The Ashvattha (sacred fig tree) — from whose roots to branches the divine manifests — is traversed from its deepest roots (leftmost) through its trunk (root) to its rightmost branches. Inorder traversal honors this natural progression: the smallest first, the greatest last, with the root balanced at the center. For a BST, this ordering reveals the divine sequence hidden within the tree's structure.