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