Problem Statement

Given root of binary tree, return the inorder traversal of the binary tree.

Morris Inorder traversal is the tree traversal algorithm aiming to achieve a space complexity of O(1) without recursion or an external data structure.

Examples

Example 1:

Input: root = [1, 4, null, 4, 2]
Output: [4, 4, 2, 1]

Example 2:

Input: root = [1, null, 2, 3]
Output: [1, 2, 3]

Different Approaches

1️⃣ Threading

Intuition:

Morris Traversal provides an efficient method for performing an in-order traversal of a binary tree without relying on recursion or an explicit stack. The core concept involves creating temporary links, referred to as "threads," between nodes to track the current position during the traversal. By establishing temporary links to each node's in-order predecessor, this approach navigates through the tree without requiring additional space. This method ensures that each node is visited in the correct sequence while maintaining the tree's original structure upon completion of the traversal.

The traversal encompasses three primary scenarios: nodes without a left child, nodes with a left child where the in-order predecessor does not have a right child, and nodes with a left child where the right child of the in-order predecessor points back to the current node. Addressing these scenarios allows for an efficient and accurate in-order traversal while preserving the tree's structure.

Approach:

1. Begin by initializing the current node to the root of the binary tree.
2. While the current node is not null:
   1. If the current node lacks a left child, print its value and move to the right child by setting the current node to its right child.
   2. If the current node has a left child:
      1. Identify the in-order predecessor of the current node, which is the rightmost node in the left subtree.
      2. If the right child of the in-order predecessor is null, create a thread by setting its right child to the current node. Then, move to the left child by updating the current node to its left child.
      3. If the right child of the in-order predecessor is not null, this indicates a previously established thread. Revert this change by setting the right child of the in-order predecessor back to null. Print the current node's value and then move to the right child by setting the current node to its right child.
3. Repeat the above steps until the traversal reaches the end of the tree.

Code:

#include<bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
  struct TreeNode {
      int data;
      TreeNode *left;
      TreeNode *right;
       TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
};

/**
    * This method performs an inorder traversal of a binary tree
    * using the Morris Traversal algorithm, which does not use
    * additional space for a stack or recursion.
*/

 
class Solution {
public:
    vector<int> getInorder(TreeNode* root) {
        // Vector to store inorder traversal
        vector<int> inorder;
        // Pointer to current node
        TreeNode* cur = root; 

        while (cur != nullptr) {
            if (cur->left == nullptr) {
                // Add current node's value and move to right child
                inorder.push_back(cur->data); 
                cur = cur->right; 
            } else {
                // Find predecessor
                TreeNode* prev = cur->left; 
                while (prev->right && prev->right != cur) {
                    prev = prev->right;
                }
                /* Establish a temporary link and move to the
                left child */
                if (prev->right == nullptr) {
                    prev->right = cur; 
                    cur = cur->left; 
                } else {
                /* Remove the temporary link, add current node's value
                and move to the right child */      
                    prev->right = nullptr; 
                    inorder.push_back(cur->data); 
                    cur = cur->right;
                }
            }
        }
        // Return inorder traversal
        return inorder; 
    }
};

int main() {
    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->left->right->right = new TreeNode(6);

    Solution sol;
    vector<int> inorder = sol.getInorder(root);

    cout << "Binary Tree Morris Inorder Traversal: ";
    for (int val : inorder) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity:O(2N), where N is the number of nodes in the Binary Tree. Each node is visited at most twice.
• Space Complexity:O(1). Morris Traversal is an in-place algorithm, using only a constant amount of extra space.