Posts Morris Traversal
Post
Cancel

Morris Traversal

PROBLEM DESCRIPTION

Binary Tree traversal using Morris Algorithm. Iterative approach, no stack required - O(1) space complexity. geeksforgeeks

SOLUTION

Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.

snapshot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    
    public List<Integer> inorderTraversal(TreeNode root) {
        
        TreeNode current = root;
        
        List<Integer> inorder = new ArrayList<>();
        
        //While current is not NULL
        while(current != null){
            
            //If the current does not have left child
            if(current.left == null){
                // a) Print current’s data
                // b) Go to the right, i.e., current = current->right
                inorder.add(current.val);
                current = current.right;
                
            }else{
                
                //Else, get the predecessor (OR node whose right child == current.)
                TreeNode pred = getPredecessor(current);
                
                //If we found right child == current
                if(pred.right == current){
                    
                    //a) Update the right child as NULL of that node whose right child is current
                    //b) Save current’s data
                    //c) Go to the right, i.e. current = current->right
                    pred.right = null;
                    inorder.add(current.val);
                    current = current.right;
                }else{
                    //a) Make current as the right child of that rightmost node we found
                    pred.right = current;
                    //b) Go to this left child, i.e., current = current->left
                    current = current.left;
                }

            }

        }
        
        return inorder;
        
    }
    
    //Get right most element in LST
    public TreeNode getPredecessor(TreeNode root){
        
        if(root.left == null) return null;
        
        TreeNode t = root.left;
        
        //t.right can be equal to root if we have already created a link to that element previously
        while(t.right != null && t.right != root){
            t = t.right;
        }
        
        return t;
        
    }
}
This post is licensed under CC BY 4.0 by the author.