# [recommend by Rainbow] Morris traversal and Time complexity analysis Why O(N) ?

• Update : 2016/02/26

about why the time complexity of the Morris traversal is O(n) maybe confusing !

Here is the details you need to understand the time complexity is O(N) as each edge is traversed for 3 times at most.

``````   Each edge is traversed at most 3 times and there are n-1 edges in a tree,
hence the O(n).
``````

I think the part that is confusing you is the predecessor finding loop because it goes down the tree following the rightmost node.

``````        /* Find the inorder predecessor of current */
pre = current->left;
while (pre->right != NULL && pre->right != current)
pre = pre->right;
``````

This full path is only processed twice:
when the current pointer reaches the node
when we have processed its left subtree

Also, the key is that this path is not processed again while we're on the left subtree.

You can see a simple example here .

https://www.quora.com/Why-does-the-Morris-in-order-traversal-algorithm-have-O-n-time-complexity

Morris traversal is a cheap way to do the traversal of the tree with no Space cost and non-recursive way.

But at first, it may seem hard for you to understand.

The key idea is to traversal as in-order, when meet the node with left child, then we will

traverse to find the pre-node of the current node and link it to the current node.

So after push back the in-order first node, it will back track by the previous setting "right link"!

So when we meet the "right link" for the next time, we will reset it and push back the value.

So we link the tree value and get the final vector result.

``````     1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left
``````

AC C++ implementation .

``````class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
TreeNode* cur, *pre;
vector<int> result;
if(!root)  return  result;

cur=root;
while(cur){
/** move left **/
if(cur->left){
/** find the previous node of the cur **/
pre=cur->left;
while(pre->right && pre->right!=cur)  pre=pre->right;
/** if not set, keep traversal **/
if(!pre->right){
pre->right=cur;
cur=cur->left;
}
/** if set, push back the value, and keep traversal **/
else{
pre->right=NULL;
result.push_back(cur->val);
cur=cur->right;
}
}
/** push_back the root value move right (previous set right link will point
to the in-order-next node)**/
else{
result.push_back(cur->val);
cur=cur->right;
}
}
}
};
``````

• Here is a in order traversal version implementation

``````class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur=root;

/** push back the left-path-node-list **/
while(cur){
st.push(cur);
cur=cur->left;
}

while(!st.empty()){
cur=st.top();
st.pop();
result.push_back(cur->val);
TreeNode* right=cur->right;
while(right){
st.push(right);
right=right->left;
}
}

return result;
}
};``````

• In my implementation, I make 2 small mistakes, here I will list the 2 points for myself.

To avoid bugs like this, it is best to mimic all the precedure in my mind before writing the code !

``````    while(cur){
if(cur->left){
pre=cur->left;
while(pre->right && pre->right!=cur){
pre=pre->right;
}
if(!pre->right){
pre->right=cur;
/** bug **/
cur=cur->left;
}
else{
pre->right=NULL;
result.push_back(cur->val);
/** bug **/
cur=cur->right;
}
}
else{
result.push_back(cur->val);
cur=cur->right;
}
}``````

• ``````class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if(!root)  return {};
vector<int> result;
TreeNode *cur=root;
stack<TreeNode*> st;
while(root) {
st.push(root);
root=root->left;
}

while(!st.empty()){
TreeNode* temp=st.top();
st.pop();

result.push_back(temp->val);
TreeNode* right=temp->right;
while(right){
st.push(right);
right=right->left;
}
}
return result;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.