# Different Node Deletion/Insertion in a Binary Search Tree

Tags:
1. Oct 23, 2016

### mooncrater

What happens, if instead of having any pointer pointing to a node's parent, we had pointer pointing to the node's successor? We know, that Searching would remain the same. But in my opinion Insertion and Deletion would change. This would happen, because in insertion, we would be needed to find the successor and predecessor of the inserted node, and changing information accordingly. And in Deletion, we would be needed to re-align the successor value of the predecessor of the deleted element.
This shows the dependency of both the modified methods on finding the predecessor of the inserted/deleted element. My pseudocode for finding the predecessor is:
Code (Text):
Predecessor(T,x)
1. y= T.root
2. while y.left_child ! = NULL
3.            y = y.left_child
4. while y.succ ! = x
5.           y = y.succ
6.return y
Here, lines 2-3 find the least element of the tree, and lines 4-5 find the element whose successor is $x$(where $x$ is the pointer to the desired node.)
As we can see, that lines 4-5 take $O(n)$ time, (where $n$ is the total number of elements) instead of $O(h)$ time.(where $h$ is the height of the tree) .
This being said, leads to a conclusion that both the methods INSERT and DELETE would take atleast $\Omega (n)$ time. But according to a question in cormen(12.3-5) [https://github.com/yaoshengzhe/notes/blob/master/clrs/12_binary_search_trees.md] [Broken] , it should be $O(h)$.
So where am I wrong?
Any help is appreciated with a lot of thankfulness. :P
Moon.

Last edited by a moderator: May 8, 2017
2. Oct 23, 2016

### anorlunda

Doesn't Knuth. Volume 3, discuss this?

3. Oct 23, 2016

### ScottSalley

The github link didn't work for me, but the description sounds like a 'threaded binary search tree'.

4. Oct 23, 2016

### Staff: Mentor

@anorlunda - Yup - Knuth does cover that. So does Cormen, so does Sedgewick in Algorithms in C Parts 1 - 4. All of which are wonderful resources!

5. Oct 25, 2016

### mooncrater

Thanks for you people replying out there. I just got the answer, and well, it's simple ( and a little embarrassing too!). My predecessor method isn't optimal. It can be made in $O(h)$. So We can get INSERT and DELETE to work in $O(h)$.
Thanks.
Moon.

6. Oct 25, 2016

### mooncrater

This might suffice.