Morris Traversal
Kundan Kumar
Software Engineer || at Businessolver|JAVA|Spring Boot|Micro Service|KAFKA|Angular|React|Data Structure|Algorithm|Problem Solving
For depth first search of tree traversal we have three traversal technique, i.e. PreOrder,InOrder and PostOrder. Either of these techniques we can traverse recursively or iteratively. For any of these techniques it took O(n) space complexity. If we want to achieve these tree traversals with O(1) space complexity then this is the Morris Traversal that helps us to achieve this task.
Morris Traversal Of PreOrder Traversal:
1. Initialize current as root
2. While current is not NULL
If the current does not have left child
a) Add current’s val into preOrderList list.
b) Go to the right, i.e., current = current->right
Else
Find rightmost node in current left subtree OR
node whose right child == current.
If we found right child == NULL
a) Add current’s val into preOrderList list.
b) Make current as the right child of that rightmost
node we found; and
c) Go to this left child, i.e., current = current->left
Else
a) Update the right child as NULL of that node whose right child is current
b) Go to the right, i.e. current = current->right
3. At Last return preOrderList.
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> preOrderList = new ArrayList<>();
TreeNode current = root;
while (current != null) {
if (current.left == null) {
preOrderList.add(current.val);
current = current.right;
} else {
TreeNode predecessor = curr.left;
while (predecessor.right != null && predecessor.right != curr) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
preOrderList.add(current.val);
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null;
current = current.right;
}
}
}
return preOrderList;
}
Morris Traversal Of InOrder Traversal:
1. Initialize current as root
2. While current is not NULL
If the current does not have left child
a) Add current’s data into inOrderList list.
b) Go to the right, i.e., current = current->right
Else
Find rightmost node in current left subtree OR
node whose right child == current.
If we found right child == NULL
a) Make current as the right child of that rightmost
node we found; and
b) Go to this left child, i.e., current = current->left
Else
a) Update the right child as NULL of that node whose right child is current
b) Add current’s val into inOrderList list.
c) Go to the right, i.e. current = current->right
3. At Last return inOrderList.
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> inOrderList = new ArrayList<>();
TreeNode current = root;
while(current != null) {
if(current.left == null) {
inOrderList.add(current.val);
current = current.right;
} else {
TreeNode predecessor = current.left;
while(predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if(predecessor.right == null){
predecessor.right = current;
current = current.left;
} else {
inOrderList.add(current.val);
predecessor.right = null;
current = current.right;
}
}
}
return inOrderList;
}
Morris Traversal Of PostOrder Traversal:
1. Initialize current as root
2. While current is not NULL
If the current does not have right child
a) Add current’s val into postOrderList list.
b) Go to the left, i.e., current = current->left
Else
Find leftmost node in current right subtree OR
node whose left child == current.
If we found left child == NULL
a) Add current’s val into postOrderList.
b) Make current as the left child of that leftmost
node we found; and
c) Go to this right child, i.e., current = current->right
Else
a) Update the left child as NULL of that node whose left child is current
b) Go to the left, i.e. current = current->right
3. reverse postOrderList.
4. At Last return postOrderList
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> postOrderList = new ArrayList<>();
TreeNode current = root;
while(current != null) {
if(current.right == null) {
postOrderList.add(current.val);
current = current.left;
} else {
TreeNode predecessor = current.right;
while(predecessor.left != current && predecessor.left != null) {
predecessor = predecessor.left;
}
if(predecessor.left == null) {
postOrderList.add(current.val);
predecessor.left = current;
current = current.right;
} else {
predecessor.left = null;
current = current.left;
}
}
}
Collections.reverse(postOrderList);
return postOrderList;
}