04.Inorder.md

🌳 Inorder Traversal in Binary Tree (BT) #94

📌 Problem Statement

Given the root of a Binary Tree, perform Inorder Traversal and return the sequence of visited nodes.

👉 Inorder Traversal Order:

Left → Root → Right

🧠 Why Inorder Traversal matters

• It’s one of the three fundamental DFS traversals

• In a Binary Search Tree, inorder traversal gives sorted order 🔥

• Helps in:

  • Tree validation (BST check)
  • Expression tree evaluation
  • Tree flattening & transformations

Think of it like:

“Check the left side first, process yourself, then check the right side” Very polite traversal 😌

👀 Example

Binary Tree:

Inorder Traversal Output

4 2 1 7 5 8 3 6

🧩 Intuition (the real understanding)

At every node:

1. Completely explore the left subtree
2. Visit the current node
3. Completely explore the right subtree

This recursive definition matches the tree’s structure perfectly. Trees and recursion are basically best friends 🤝.

🐌 Brute Force Approach (conceptual)

There’s no real “brute force” traversal, but beginners often:

• Recompute paths
• Use unnecessary arrays
• Or simulate recursion badly

Still ends up O(N), but messy and inefficient.

👉 Better approach: use recursion or a stack cleanly.

✅ Optimal Approaches

We’ll cover three versions:

1. Recursive (most intuitive)
2. Iterative using Stack (interview favorite)
3. Morris Traversal (O(1) space, big-brain mode 🧠)

1️⃣ Recursive Inorder Traversal 🌱 (Most intuitive)

🧠 Idea

Use recursion to:

• Traverse left
• Process root
• Traverse right

💡 Algorithm

If root is NULL:
    return

Inorder(root.left)
Visit root
Inorder(root.right)

💻 Code (C++)

void inorder(Node* root, vector<int>& result) {
    if (!root) return;

    inorder(root->left, result);
    result.push_back(root->val);
    inorder(root->right, result);
}

✅ Why this works

• Tree is recursive by nature
• Each node is visited exactly once
• Very readable and clean ✨

⏱ Complexity

• Time: O(N)
• Space: O(H) (H = height of tree, recursion stack)

2️⃣ Iterative Inorder Traversal (Using Stack) 🧱

🔥 Interviewers LOVE this one

🧠 Intuition

We manually simulate recursion using a stack:

• Go as left as possible
• Process node
• Move right

Like retracing steps in a maze 🗺️

💡 Algorithm

1. Initialize empty stack

2. Set current = root

3. While current != NULL or stack not empty:

   • Push all left nodes
   • Pop stack, process node
   • Move to right child

💻 Code (C++)

vector<int> inorderTraversal(Node* root) {
    vector<int> result;
    stack<Node*> st;
    Node* curr = root;

    while (curr != nullptr || !st.empty()) {
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }

        curr = st.top();
        st.pop();
        result.push_back(curr->val);

        curr = curr->right;
    }

    return result;
}

⏱ Complexity

• Time: O(N)
• Space: O(H) stack

💬 Interview Tip

If recursion is banned ❌ → This is your go-to solution.

3️⃣ Morris Inorder Traversal 🌟 (O(1) Space)

“I bend the tree, but I don’t break it.” – Morris Traversal (probably)

🧠 Idea

• Temporarily create threads to predecessor
• Avoid stack & recursion
• Restore tree after traversal

💡 Algorithm (High-level)

1. If left child is NULL → visit node, move right

2. Else:

   • Find inorder predecessor
   • Create temporary link
   • Traverse left

3. Remove link after use

💻 Code (C++)

vector<int> inorderMorris(Node* root) {
    vector<int> result;
    Node* curr = root;

    while (curr) {
        if (!curr->left) {
            result.push_back(curr->val);
            curr = curr->right;
        } else {
            Node* prev = curr->left;
            while (prev->right && prev->right != curr)
                prev = prev->right;

            if (!prev->right) {
                prev->right = curr;
                curr = curr->left;
            } else {
                prev->right = nullptr;
                result.push_back(curr->val);
                curr = curr->right;
            }
        }
    }
    return result;
}

⏱ Complexity

• Time: O(N)
• Space: O(1) 😎

⚠️ Warning

• Harder to implement
• Easy to mess up
• Use only when space is critical

🧪 Test Cases

Tree	Output
Empty tree	[]
Single node	[1]
Skewed left	increasing order
Skewed right	same as preorder
BST	Sorted output

🧠 Key Observations

• Inorder traversal of BST = sorted array
• Stack size depends on tree height
• Morris traversal modifies tree temporarily

🚀 Variations & Related Problems

• Validate Binary Search Tree
• Kth smallest element in BST
• Recover BST
• Flatten binary tree
• Inorder successor / predecessor

❓ FAQs

Q1: Why is inorder important for BST?

Because BST property ensures:

Left < Root < Right

So inorder gives sorted values 📈

Q2: Which inorder approach should I use in interviews?

• Recursive → clarity
• Iterative → preferred
• Morris → flex 💪 (only if asked)

Q3: Can inorder be done without recursion or stack?

Yes, Morris Traversal

Q4: Does inorder traversal work the same for BT and BST?

Traversal order is same, but meaning differs Only BST guarantees sorted output.

Q5: What if tree height is very large?

Avoid recursion → use iterative

🧠 Quick Revision Cheat Sheet 📝

Inorder = Left → Root → Right
Recursive = clean
Iterative = stack
Morris = O(1) space
BST inorder = sorted