It will take two keys as input key1 and key2 and finds the node with key1, then changes it to key2. This may disturb the BST property (of having smaller things to the left and bigger to the right); this function should make appropriate changes in tree so that it becomes BST again.

I tried making links of the new data with links of the older node to be replaced with ,but I can organize my tree precisely.

CodePudding user response：

The easiest way is to find the LCA of key1 and key2, then delete key1 and key2 sequentially and lastly, add their values back to the subtree rooted in the LCA.

If the LCA is either key1 or key2, use the root of the whole tree as the LCA.

If key1 or key2 is the LCA and also the root of the whole tree, just return the original tree before the swap.

This will give you a possibly different tree. Since you didn't specify a criteria for how the tree should be organized after the swap, this is a possibility. Total complexity should be O(n).

CodePudding user response：

I kind of agree with @Daniel except for the fact that key2 is not in your tree.

In your question, remove the use of the word "swap" and instead say replace. I think this is responsible for creating the idea that you want to swap (exchange) two nodes.

For this problem, simply remove the node with key1 in it and insert a new node with key2. Here I am assuming you already have the code in place to do these things