Inorder Traversal of Binary Tree

Description
Inorder traversal of a binary tree follows the order: first visit the left subtree, then the root node, and finally the right subtree. For a Binary Search Tree (BST), the result of inorder traversal is the node values arranged in ascending order. This traversal is a fundamental and frequently tested topic in interviews, typically requiring both recursive and iterative solutions.

Step 1: Recursive Solution
The recursive solution directly follows the definition of inorder traversal:

1. Recursively traverse the left subtree;
2. Visit the root node;
3. Recursively traverse the right subtree.

Code Framework (C++ Example):

void inorderTraversal(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    inorderTraversal(root->left, result);  // First recurse on left subtree
    result.push_back(root->val);           // Visit the root node
    inorderTraversal(root->right, result); // Finally recurse on right subtree
}

Key Points:

• The recursion termination condition is when the node is empty (nullptr);
• Note that result needs to be passed by reference to store the results.

Step 2: Iterative Solution (Using a Stack to Simulate Recursion)
The essence of recursion is the function call stack. The iterative method simulates this process using an explicit stack:

1. Starting from the root node, push all left child nodes onto the stack until reaching the leftmost node;
2. Pop the top node from the stack (the current leftmost node) and visit it;
3. Turn to the right subtree of this node and repeat Step 1.

Code Implementation:

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> stk;
    TreeNode* cur = root;
    
    while (cur != nullptr || !stk.empty()) {
        // Traverse to the leftmost node, pushing all nodes along the path onto the stack
        while (cur != nullptr) {
            stk.push(cur);
            cur = cur->left;
        }
        // Pop the top and visit it
        cur = stk.top();
        stk.pop();
        result.push_back(cur->val);
        // Turn to the right subtree
        cur = cur->right;
    }
    return result;
}

Key Points:

• The outer loop condition is cur is not null or stack is not empty, ensuring complete traversal;
• The inner loop is responsible for going left, while the outer loop handles the right subtree.

Step 3: Morris Inorder Traversal (Space Complexity O(1))
Morris traversal uses the null pointers of leaf nodes to temporarily store relationships, avoiding the use of a stack:

1. If the current node cur has no left subtree, directly visit cur and move to the right subtree;
2. If cur has a left subtree, find the rightmost node in the left subtree (i.e., the predecessor node of cur):
   • If the right pointer of the predecessor node is null, set it to point to cur (establish a temporary link), then move cur to the left;
   • If the right pointer of the predecessor node points to cur (indicating the left subtree has been visited), then break the link, visit cur, and move to the right subtree.

Code Implementation:

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    TreeNode* cur = root;
    
    while (cur != nullptr) {
        if (cur->left == nullptr) {
            // No left subtree, visit current node and move to right subtree
            result.push_back(cur->val);
            cur = cur->right;
        } else {
            // Find the rightmost node in the left subtree (predecessor node)
            TreeNode* prev = cur->left;
            while (prev->right != nullptr && prev->right != cur) {
                prev = prev->right;
            }
            if (prev->right == nullptr) {
                // Establish temporary link and continue traversing left
                prev->right = cur;
                cur = cur->left;
            } else {
                // Break the link, visit current node, and move to right subtree
                prev->right = nullptr;
                result.push_back(cur->val);
                cur = cur->right;
            }
        }
    }
    return result;
}

Key Points:

• Temporarily modifies the tree structure by altering pointers and restores it after traversal;
• Each node is visited twice (first to establish the link, second to break it), but the time complexity remains O(n).

Summary

• The recursive method is intuitive but risks stack overflow;
• The iterative method explicitly manages a stack, suitable for understanding the traversal process;
• The Morris method saves space but temporarily modifies the tree structure.