Merge Two Balanced Binary Search Trees


  • 1
    H

    Merge Two Balanced Binary Search Trees


  • 0
    B

    @haochenliu
    Here is my Solution:
    Time Complexity:O(n+m)
    Space Complexity:O (height of tree1 + height of tree2)

    /* The structure of Node is
    struct Node {
    int data;
    Node * right, * left;
    };*/
    
    
    void merge(Node *root1, Node *root2)
    {
        Node* curr1=NULL;
        Node* curr2=NULL;
        int flag1=1;
        int flag2=1;
        
        
        stack<Node*> s1,s2;
        while(1)
        {
           //  Like inorder of first Tree
            while(flag1)
            {
                while(root1)
                {
                    s1.push(root1);
                    root1=root1->left;
                }
                if(!s1.empty())
                {
                    curr1=s1.top();
                    s1.pop();
                    root1=curr1->right;
                    break;
                }
                else
                {
                    curr1=NULL;
                    break;
                }
            }
            
            
             //  Like inorder of second Tree
            while(flag2)
            {
                while(root2)
                {
                    s2.push(root2);
                    root2=root2->left;
                }
                if(!s2.empty())
                {
                    curr2=s2.top();
                    s2.pop();
                    root2=curr2->right;
                    break;
                }
                else
                {
                    curr2=NULL;
                    break;
                }
            }
            
            // now comparing curr1 and cuur2 and deciding from 
            //which tree next element will come
            
            
            if(curr1==NULL && curr2==NULL)
                break;
            else if(curr1==NULL)
            {
                cout<<curr2->data<<" ";
                flag1=0;
                flag2=1;
            }
            else if(curr2==NULL)
            {
                cout<<curr1->data<<" ";
                flag2=0;
                flag1=1;
            }
            else if(curr1->data>curr2->data)
            {
                cout<<curr2->data<<" ";
                flag1=0;
                flag2=1;
            }
            else
            {
                cout<<curr1->data<<" ";
                flag2=0;
                flag1=1;
            }
            
        }
        
      cout<<endl;
    }
    
    

Log in to reply
 

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