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


  • 4

    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;
                }
            }
        }
    };
    

  • 0

    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;
        }
    };

  • 0

    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;
            }
        }

  • 0
    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;
        }
    };

Log in to reply
 

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