morris inorder traversal python

1  public class TreeNode
2    {
3        public int val;
4        public TreeNode left;
5        public TreeNode right;
6
7        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
8        {
9            this.val = val;
10            this.left = left;
11            this.right = right;
12        }
13    }
14
15    class MorrisTraversal
16    {
17        public static IList<int> InOrderTraversal(TreeNode root)
18        {
19            IList<int> list = new List<int>();
20            var current = root;
21            while (current != null)
22            {
23                //When there exist no left subtree
24                if (current.left == null)
25                {
26                    list.Add(current.val);
27                    current = current.right;
28                }
29                else
30                {
31                    //Get Inorder Predecessor
32                    //In Order Predecessor is the node which will be printed before
33                    //the current node when the tree is printed in inorder.
34                    //Example:- {1,2,3,4} is inorder of the tree so inorder predecessor of 2 is node having value 1
35                    var inOrderPredecessorNode = GetInorderPredecessor(current);
36                    //If the current Predeccessor right is the current node it means is already printed.
37                    //So we need to break the thread.
38                    if (inOrderPredecessorNode.right != current)
39                    {
40                        inOrderPredecessorNode.right = null;
41                        list.Add(current.val);
42                        current = current.right;
43                    }//Creating thread of the current node with in order predecessor.
44                    else
45                    {
46                        inOrderPredecessorNode.right = current;
47                        current = current.left;
48                    }
49                }
50            }
51
52            return list;
53        }
54
55        private static TreeNode GetInorderPredecessor(TreeNode current)
56        {
57            var inOrderPredecessorNode = current.left;
58            //Finding Extreme right node of the left subtree
59            //inOrderPredecessorNode.right != current check is added to detect loop
60            while (inOrderPredecessorNode.right != null && inOrderPredecessorNode.right != current)
61            {
62                inOrderPredecessorNode = inOrderPredecessorNode.right;
63            }
64
65            return inOrderPredecessorNode;
66        }
67    }
68

1class Solution(object):
2def inorderTraversal(self, current):
3    soln = []
4    while(current is not None):    #This Means we have reached Right Most Node i.e end of LDR traversal
5
6        if(current.left is not None):  #If Left Exists traverse Left First
7            pre = current.left   #Goal is to find the node which will be just before the current node i.e predecessor of current node, let's say current is D in LDR goal is to find L here
8            while(pre.right is not None and pre.right != current ): #Find predecesor here
9                pre = pre.right
10            if(pre.right is None):  #In this case predecessor is found , now link this predecessor to current so that there is a path and current is not lost
11                pre.right = current
12                current = current.left
13            else:                   #This means we have traverse all nodes left to current so in LDR traversal of L is done
14                soln.append(current.val) 
15                pre.right = None       #Remove the link tree restored to original here 
16                current = current.right
17        else:               #In LDR  LD traversal is done move to R  
18            soln.append(current.val)
19            current = current.right
20
21    return soln
22