# Morris Traversal------- NO RECURSION NO STACK

• ``````public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null) return new ArrayList<Integer>();
List<Integer> res = new ArrayList<Integer>();
TreeNode pre = null;
while(root != null){
if(root.left == null){
root = root.right;
}else{
pre = root.left;
while(pre.right != null && pre.right != root){
pre = pre.right;
}
if(pre.right == null){
pre.right = root;
root = root.left;
}else{
pre.right = null;
root = root.right;
}
}
}
return res;
}
}``````

• Similar code. Morris traversal can do inorder and preorder. Postorder with Morris traversal is challenging. Google morris traversal for more info.

Morris traversal can also be used to solve Recover binary search tree problem.

Code:

``````vector<int> inorderTraversal(TreeNode *root) {
vector<int> ret;
if(!root) return ret;
TreeNode* walker = root;
while(walker) {
if(walker->left) {
TreeNode* walker2 = walker->left;
while(walker2->right && walker2->right != walker) walker2 = walker2->right;
if(!walker2->right) {
walker2->right = walker;
walker = walker->left;
}
else {
walker2->right = NULL;
ret.push_back(walker->val);
walker = walker->right;
}
continue;
}
ret.push_back(walker->val);
walker = walker->right;
}
return ret;
}
``````