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:

`50 \ 60 \ 90`

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).

The way I see it, why don't you do an inorder traversal of b. Then, until the array is not empty, do a regular delete from a for the value of the array index. Traversal is O(n) and deletion for each index will be O(logn). Totally, this operation will be O(nlogn).

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.

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

Similar Questions

I have problem with method MoveNext in my enumerator. I need iterator for binary search tree. In construcotr of my enumerator I initialize Node to root of tree. Current is value that I ened to return

I'm working on this homework where I need to print my binary search tree in preorder, postorder, and inorder. However, it seems like only my inorder method is working. I have used the following test c

Does anyone know how to figure out search time for a binary search tree(i.e. worst-case, best-case, and average-case)?

so i need to implement a member function, pre-order and inorder traversal of a binary search tree using recursion. i'm having trouble implementing all three, since they're coming out with the wrong ou

Please help I've been trying to generate a random binary search tree of size 1024 and the elements needs to be random sortedset ... I'm able to write a code to create a binary search tree manually by

When programming a simple binary search tree data structure (non self-balancing), the advice most resources give when deleting a node with two children is to copy the data out of one of the left child

Do you know, please, if C++ STL contains a Binary Search Tree (BST) implementation, or if I should construct my own BST object? In case STL conains no implementation of BST, are there any libraries av

i have implement binary search tree in c++ #include <iostream> #include <cstdlib> using namespace std; class binary{ private: struct tree{ tree *left; tree *right; int data; }; tree *root;

I'm reading up on Binary Search Trees and I have a question to answer similar to Ordered Binary Tree of Strings Are the trees I've drawn below correct for before and after balancing? The data being en

I am still fairly new to generics and binary search trees, and I am trying to add a custom Student object to a BST, and don't know exactly how to go about implementing it. I have my Student class decl

Search(T,k) x<- root[T] while x != NULL and k != key[x] do if k<key[x] then x <- left[x] else x <- right[x] return x I just started with algorithms and I often see <- this and key[x]

I'm wondering, is there any difference between performance of those, provided binary search is used for sorted linked list insertion, search. And in which situations they perform differently or maybe

So I've looked around a lot for some information on how to take elements from a binary search tree and write them to a file, and then later read them back into the tree as a type of load function. I

Suppose i am having an array say 1 5 4 6 8 9 10 22 17 7 9 3 I want to create a binary search tree from this array. I need algorithm to understand that. I have read rest other things related to BST l

Im trying to insert into an array Based Binary Search tree. I am not sure how i prevent overwriting data using left and right indexes... Do i insert leftchild as tree[2 * i + 1] and rightchild as tre

I was wondering if we can use a binary search tree to simulate heap operations (insert, find minimum, delete minimum), i.e., use a BST for doing the same job? Are there any kind of benefits for doing

I am trying to implement a binary search tree in python, but I can't find a solution for delete. If the item is in a leaf, that is simple, but what if the item I want to delete has 2 children which al

I need a function for 'smart' search which will return number of elements in binary tree which are greater then given parameter but wont go through all nodes. For example, if i want to find number of

My linked list structure is typedef struct ll { int data; struct ll *left; struct ll *right; }node; My function for deleting is void delete(node **parent,node **root,int n) { if((*root)==NULL) //if

I read about binary search trees that if it is a complete tree (all nodes except leaf nodes have two children) having n nodes, then no path can have more than 1+log n nodes. Here is the calculation I

I would like to find the most efficent way to check the node with minimum value in a Binary Search Tree. I'm not thinking to do it in a certain programming language right now, I would like just to thi

I'm reading the Cormen algorithms book (binary search tree chapter) and it says that there are two ways to traverse the tree without recursion: using stack and a more complicated but elegant solution

I'm learning Data Structures & Algorithms now. My lecture notes have an implementation of a binary search tree which is implemented using a recursive method. That is an elegant way, but my questio

others say that for making a binary search tree with an array of {3,7,1,90,45,67,54,23,...} it is good to work with TreeSet.but my code below will throw an exception and I don't know why? my array lis

I am implementing a Binary Search tree in C++ I have the following code to add an entry to the tree: void tree::add(int n) { int found; leaf *t,*parent; findparent(n,found,parent); if(found==YES) cout

In a binary search tree if you are along a certain search path, what keys are considered to be on the left of the path and which on the right? For example if my tree is : 25 12 30 10 15 28 32 14 20

As far as I know the time complexity between AVL trees and Binary Search Trees are the same in average case, with AVLs beating BSTs in worst case scenarios. This gives me a hint that AVLs are always s

If I delete node x and then node y or delete y and the x, after this deleted I will stay with the same binary search tree? I tried a few examples and I think that's true. But how can i prove this?

Given an arbitrary set of values V and building a tree by inserting values left to right, what does it mean if I'm asked if my orderings of these values (to construct a minimum height and maximum heig

So when i delete in binary search tree, do i need to have like 7 different cases i.e. 1.Left Leaf; 2.Right Leaf; 3.Left child with only left child.//i.e the node to be deleted is the left child of it'

I'm doing a small Java work on Binary Search Tree but when I'm implementing the recursive insert of a node into the tree and display it, I don't get anything. I've been on it for a while now, I don't

I'm implementing the insert function of a BST, below is my code: data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq) tinsert :: Tree a -> a -> Tree a tinsert Empty a = Branch a

I want to make a generic BST, that can be made up of any data type, but i'm not sure how I could add things to the tree, if my BST is generic. All of my needed code is below. I want my BST made up of

I am having trouble outputting a binary search tree. I have to build the tree, and then place all the doubles from the tree in order into a vector, and then output that vector in order. The problem I

want to insert element in binary tree. what is wrong in this code. I have a structure with data, left and right as self referencing structure and root as a global variable of type structure initialize

I am trying to write a delete for a binary tree and this is the function I wrote along with my data structure: class node{ public: int value; node* left; node* right; ~node(); }; class tree{ public:

Need help to figure out why the following code for basic Binary Search Tree insertion is not working. Since I have been working on C# for sometime now, I'm afraid I forgot some of my C++. Also, any su

I've been searching for how to calculate the height of a Binary Search Tree and my research has lead me to the following implementation. I'm still trying to wrap my head around why it should work, but

How much does it cost the search operation in a Binary tree? Is it O(n)?

Given a binary tree, I want to find out the largest subtree which is a BST in it. This question is duplicate of Finding the largest subtree in a BST, where 1337c0d3r gives a O(n) solution by traversi

First i insert the tree into an array according to Level order (aka Breadth first) traversal. and now i check the array For i=1 to Len(Array) do: IF 2*i smaller than Len(Array) then: IF Array[i] smal

I am trying to traverse a binary search tree in-order, and place the data (sorted) in an array. for some reason, the pointer to the current position in the array is not moving right. This is the decle

Guys I'm trying to implement deletion algorithm for a Red Black tree and I'm having problem with understanding line three of this algorithm (from a book Introduction to Algorithms second edition):

I've given the result of in-order traversal of a binary tree (not binary search tree) as: E, D, B, A, G, F, H, C Now I've to find out the result of the post-order traversal of the same tree for which

Possible Duplicate: Where is binary search used in practice? What are the applications of binary trees? I have done various exercises involving adding,deleting,ordering and so on. However i am havin

This is probably a simple task for expert coders, but is it possible to recursively traverse a binary unordered tree to find a node? I can do this for a binary search tree, but I'm struggling with how

This is a code to delete a node from a Binary Search Tree: My question is: Why do we pass the node pointer by reference to DelSingle function but we only pass a node pointer to DelDoubleByCopying func

I am reviewing for my final and one of the practice problem asks to implement a function that puts a value into a binary search tree in Python. Here is the Tree implementation I am using. class Tree(o

I'm using a binary search tree that collects strings and then orders them in post order. I also use a list that shows the line number where the string appears. I can make the BST work properly however

I'm trying to write a size() method for a polymorphic binary search tree. I.e. A BST that has classes EmptyTree and NonEmptyTree that both implement a tree interface. EmptyTree is being used to repr