deletion in a binary search tree

Question

I have been given two binary search trees. For example, A and B. Next, I was asked to delete the tree B from the tree A.

By deletion, I mean delete all the nodes present in B from A. Note: B is not necessarily a subtree of A.

eg:
A:

      50   
     / \  
    10  75  
   /   / \  
  1   60   90

B:

     10
     / \
    1   75

Resulting tree should be:

Two approaches came to my mind:
A1:
node* deleteTree(node* A, node* B) ;
Take the root of tree B. Delete this node from tree A(by normal BSt deletion method). Next divide the problem into two parts - for the left subtree of B and the right subtree of B. For each of the subtree, recurse. For the left subtree, the node which occupied the node which was deleted should serve as the root for tree A. For the right subtree, the inorder successor of the deleted node should server as the root for tree A.

A2: The other approach is a little weird. I find the inorder and preorder traversal of tree A. Find and delete all the nodes in tree B using binary search along with recursion(we dont modify the preorder). Finally recostruct our bst from the inorder(remaining) and the preorder(unchanged).

Prob A: Find an efficient way for BST.
Prob B: Find an efficient way for any Binary tree(not just BST).

so what is your question? also, i think your leaf in the resulting tree should be 90 and not 70. — Dhruv Gairola

Mu Qiao Mu Qiao · Accepted Answer · 2011-08-31T13:12:58

Problem A

I assume the two trees are balanced.

void deleteTree(node* A, node* B)
{
    if(A == NULL || B == NULL)
        return;

    if(A->data == B->data)
    {
        deleteTree(A->left, B->left);
        deleteTree(A->right, B->right);
        removeNode(A); // Normal BST remove
    }
    else if(A->data > B->data)
    {
        Node* right = B->right;
        B->right = NULL;
        deleteTree(A->left, B);
        deleteTree(A, right);
    }
    else // (A->data < B->data)
    {
        Node* left = B->left;
        B->left = NULL;
        deleteTree(A->right, B);
        deleteTree(A, left);
    }
}

Time complexity:

T(N) = 2 * T(N / 2) + O(1)

So the overall complexity is O(N) according to master theorem. The space complexity is O(1). One drawback is I destructed B.

PS: I don't have a BST implementation at hand so I can't test the code for you. But I think the idea is correct.

Problem B

Use hash table for one tree and traverse another. You will get O(N) for both time and space complexity.

deletion in a binary search tree

2 Answers

Problem A

Problem B