Problem Statement

Given a binary tree, the task is to traverse all its nodes in a specific order known as inorder traversal. In inorder traversal, the nodes are visited in the following order: left child, root, right child.

Examples

Example 1:

Consider the following binary tree:

       1
     /   \
    2     3
   / \   / \
  4   5 6   7

The inorder traversal of this tree would be 4, 2, 5, 1, 6, 3, 7.

Different Approaches

There are several approaches to perform inorder traversal of a binary tree. We will discuss three common approaches:

1. Recursive Approach
2. Iterative Approach using Stack
3. Morris Traversal

1 Recursive Approach:

Algorithm InorderTraversal(root):
    1. If root is not null:
        a. Recursively traverse the left subtree by calling InorderTraversal(root->left).
        b. Visit (print, process, etc.) the value of the root node.
        c. Recursively traverse the right subtree by calling InorderTraversal(root->right).

This algorithm follows a depth-first traversal strategy, where we visit the left subtree, then the root node, and finally the right subtree.

2 Iterative Approach:

1. Start with an empty stack and initialize a pointer curr to the root of the binary tree.
2. Loop until curr is not null or the stack is not empty:
   1. While curr is not null, push curr onto the stack and move curr to its left child (to explore the left subtree).
   2. If curr becomes null (indicating that we have traversed the left subtree completely):
      1. Pop the top node from the stack. This node represents the current root of a subtree.
      2. Visit (print, process, etc.) the value of the popped node.
      3. Move curr to the right child of the popped node (to explore the right subtree).

Algorithm InorderTraversal(root):
    1. Create an empty stack.
    2. Initialize a pointer 'curr' to root.
    3. While curr is not null or the stack is not empty:
        a. While curr is not null:
            i. Push curr onto the stack.
            ii. Move curr to its left child (curr = curr->left).
        b. If curr is null:
            i. Pop the top node from the stack and let it be 'curr'.
            ii. Visit (print, process, etc.) the value of 'curr'.
            iii. Move curr to its right child (curr = curr->right).

In this algorithm, we simulate the function call stack of the recursive approach using an explicit stack data structure. We push nodes onto the stack as we traverse the left subtree, and when we encounter a null pointer, we pop a node from the stack, visit it, and then move to its right child.

Illustration:

Consider the following binary tree:

       1
     /   \
    2     3
   / \   / \
  4   5 6   7

1 We start with an empty stack and set curr to the root node, which is 1.

2. We push 1 onto the stack and move curr to its left child child, which is 1.

Stack: 1
curr: 2

3 We push 2 onto the stack and move curr to its left child, which is 4.

Stack: 1, 2
curr: 4

4 Since 4 doesn't have a left child, we pop 4 from the stack, visit its value (print 4), and move curr to its right child, which is null.

Stack: 1, 2
curr: null

5 Since curr is null, we pop 2 from the stack, visit its value (print 2), and move curr to its right child, which is 5.

Stack: 1
curr: 5

6 We push 6 onto the stack and move curr to its left child, which is null.

Stack: 1, 5
curr: null

7 Since curr is null, we pop 5 from the stack, visit the value (print 5), and move curr to its right child, which is null.

Stack: 1
curr: null

8 Since curr is null and stack is not empty, we pop 1 from the stack, visit its value (print 1), and move curr to its right child, which is 3.

Stack: 
curr: 3

9 We push 3 onto the stack and move curr to its left child, which is 6.

Stack: 3
curr: 6

10 We push 6 onto the stack and move curr to its left child, which is null.

Stack: 3, 6
curr: null

11 Since curr is null, we pop 6 from the stack, visit its value (print 6), and move curr to its right child, which is null.

Stack: 3
curr: null

12 Since curr is null and the stack is not empty, we pop 3 from the stack, visit its value (print 3), and move curr to its right child, which is 7.

Stack: 
curr: 7

13 We push 7 onto the stack and move curr to its left child, which is null.

Stack: 7
curr: null

14 Since curr is null, we pop 7 from the stack, visit its value (print 7), and move curr to its right child, which is null.

Stack: 
curr: null

15 Now, curr is null, and the stack is empty, so the traversal is complete.

3 Morris Inorder Traversal

Code Implementation

1 Recursive Approach

#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->val << " ";
        inorderTraversal(root->right);
    }
}

int main() {
    // Constructing the binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    std::cout << "Inorder Traversal: ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

2 Iterative Approach using Stack

#include <iostream>
#include <stack>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorderTraversal(TreeNode* root) {
    std::stack<TreeNode*> st;
    TreeNode* curr = root;
    while (curr != nullptr || !st.empty()) {
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top();
        st.pop();
        std::cout << curr->val << " ";
        curr = curr->right;
    }
}

int main() {
    // Constructing the binary tree (same as above)
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    std::cout << "Inorder Traversal: ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

Complexity Analysis

1 Recursive Approach:

• Time Complexity: O(n)
  • In the worst-case scenario, where the binary tree is completely unbalanced (skewed), the recursive function will visit every node once, resulting in n operations, where n is the number of nodes in the tree.
• Space Complexity: O(h)
  • The space complexity is determined by the height of the binary tree, h, since the recursive function calls will create a function call stack with a maximum depth equal to the height of the tree.

2 Iterative Approach using Stack:

• Time Complexity: O(n)
  • Similar to the recursive approach, the iterative approach visits every node once, resulting in n operations in the worst-case scenario.
• Space Complexity: O(h)
  • The space complexity is determined by the height of the binary tree, h, since the stack will store nodes up to the height of the tree. In the worst-case scenario, where the tree is completely unbalanced, the space complexity is O(n). However, in a balanced tree, the space complexity is O(logn).