Morris Inorder Traversal

Binary Trees Traversal in Constant Space Hard

Fun Fact: The underlying concept of an Inorder Tree Traversal, including the optimized Morris Inorder Traversal, has extensive practical applications in database systems
Database storage and querying often utilize B-trees and B+ trees, which are generalized binary trees
Thus, Inorder Traversal is used to retrieve items from these trees in a sorted manner
This is crucial for operations like range queries or sorted output which forms the backbone of database manipulation languages like SQL

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

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

Examples:

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

Output : [4, 4, 2, 1]

Explanation :

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

Output : [1, 3, 2]

Explanation :

Input : root = [5, 1, 2, 8, null, 4, 5, null, 6]

Constraints

1 <= Number of Nodes <= 100
-100 <= Node.val <= 100

Hints

Instead of using a stack, it modifies the tree structure temporarily by creating threaded links using the rightmost node of the left subtree.
Instead of using a stack, it modifies the tree structure temporarily by creating threaded links using the rightmost node of the left subtree.

Company Tags

Epic Systems Visa Zoho Shopify Lyft Ernst & Young Morgan Stanley Western Digital GE Healthcare Salesforce eBay Unity Technologies Stripe Qualcomm Robinhood Swiggy MongoDB Byju's Boston Consulting Group Cloudflare Oracle Flipkart IBM Cerner Bloomberg Google Microsoft Amazon Meta Apple Netflix Adobe

Editorial

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:

Begin by initializing the current node to the root of the binary tree.
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.
Repeat the above steps until the traversal reaches the end of the tree.

Refer to the video for the dry run.

Solution:

#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;
}
// Definition for a binary tree node.
  public class TreeNode {
      int data;
      TreeNode left;
      TreeNode right;
      TreeNode(int val) { data = val; left = null; right = null; }
  }

/**
    * 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 List<Integer> getInorder(TreeNode root) {
        // List to store inorder traversal
        List<Integer> inorder = new ArrayList<>(); 
        // Pointer to the current node
        TreeNode cur = root; 

        while (cur != null) {
            if (cur.left == null) {
                // Add current node's value and move to right child
                inorder.add(cur.data); 
                cur = cur.right; 
            } else {
                // Find the predecessor
                TreeNode prev = cur.left; 
                while (prev.right != null && prev.right != cur) {
                    prev = prev.right;
                }

                /* Establish a temporary link and move to the
                left child */
                if (prev.right == null) {
                    prev.right = cur; 
                    cur = cur.left; 
                } else {
                /* Remove the temporary link, add current node's value
                and move to the right child */    
                    prev.right = null; 
                    inorder.add(cur.data); 
                    cur = cur.right; 
                }
            }
        }
        // Return inorder traversal
        return inorder; 
    }
}

// Example usage:
public class Main {
    public static void main(String[] args) {
        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 = new Solution();
        List<Integer> inorder = sol.getInorder(root);

        System.out.print("Binary Tree Morris Inorder Traversal: ");
        for (int val : inorder) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

# 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:
    def getInorder(self, root):
        # List to store inorder traversal
        inorder = []  
        # Pointer to current node
        cur = root  

        while cur is not None:
            if cur.left is None:
                # Add current node's value and move to right child
                inorder.append(cur.data)  
                cur = cur.right  
            else:
                # Find predecessor
                prev = cur.left  
                while prev.right and prev.right != cur:
                    prev = prev.right
                
                if prev.right is None:
                    # Establish temporary link
                    prev.right = cur 
                    # Move to left child 
                    cur = cur.left  
                else:
                    # Remove temporary link
                    # Add current node's value 
                    # Move to right child
                    prev.right = None  
                    inorder.append(cur.data)  
                    cur = cur.right  
                    
        # Return inorder traversal
        return inorder  

if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.left.right.right = TreeNode(6)

    sol = Solution()
    inorder = sol.getInorder(root)

    print("Binary Tree Morris Inorder Traversal:", end=" ")
    for val in inorder:
        print(val, end=" ")
    print()
// Definition for a binary tree node.
class TreeNode {
      constructor(val = 0, left = null, right = null){
          this.data = val;
          this.left = left;
          this.right = right;
      }
 }

/**
    * 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 {
    getInorder(root) {
        // Array to store inorder traversal
        let inorder = []; 
        // Pointer to current node
        let cur = root;

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

// Example usage:
let 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);

let sol = new Solution();
let inorder = sol.getInorder(root);

console.log("Binary Tree Morris Inorder Traversal:", inorder.join(" "));

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.

Code

Problem List