This week's book giveaway is in the Kotlin forum.We're giving away four copies of Kotlin in Action and have Dmitry Jemerov & Svetlana Isakova on-line!See this thread for details.
Win a copy of Kotlin in Action this week in the Kotlin forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Binary Tree remove node algorithms

KR Campbell
Ranch Hand
Posts: 124
Hi,
I'm playing around with binary trees at the minute and having one of those periods where I am wondering whether I have been lobotomised in my sleep. I'm trying to think of algorithms for removing an element from a binary tree. At the minute all I can come up with is this:
Case: node is an internal node.
1. Search for the node ( left subtree < value, right subtree > value)
2. (if !=null) Connect the right subtree of node to node's parent in place of node.
3. Keep a reference, temp, to the left subtree of node.right and reconnect
the left subtree of node as the left subtree of node.right.
4. Add() each of the nodes in temp to node.right.
5. node=null.
Does anyone know of a more efficient general algorithm?
Regards,
Kenny

Stefan Wagner
Ranch Hand
Posts: 1923
I didn't do much about trees, but couldn't you just:
3. Find the leftmost node in the old_right_subtree=new subtree.
4. Connect the removed left_subtree to this node (left).
since the order in the left subtree isn't changed, it needn't be added node by node I guess.

KR Campbell
Ranch Hand
Posts: 124
Hi,

Thanks, but I think the problem with that is that the removed node has a left subtree and the right node that is moving up to replace it also has a left subtree. They need to be merged somehow.
For example:

Regards,
Ken

KR Campbell
Ranch Hand
Posts: 124
Hi,

Thanks, but I think the problem with that is that the removed node has a left subtree and the right node that is moving up to replace it also has a left subtree. They need to be merged somehow.
For example:
15
/ \
9 23
/ \ / \
6 12 22 24
/ \ / \
1 7 11 14
Supposing I want to remove node with value 9. If I move 12 up to replace it
what do I do with 11? In fact, looking at this I just realised that I have to do it the other way round. Its 9's left subtree that needs to be added to 11 to keep the order.
I still feel that I'm missing something.

Regards,
Ken

KR Campbell
Ranch Hand
Posts: 124
Oh.. that's what you were saying.
Thanks.
Ken