java binary search tree

Question

Hello. I have a question about how would I remove a child from a node (root)? Since I can't call remove, if I make the child null, will the children of that child move up? Like, would I just initialize it as null?? Or would I point to the child's child?

Answer 1

In a traditional binary search tree, removal of a node can have different consequences depending on how many children the node has:

• A node with no children can simply be removed
• A node with one child can be removed, and the node will be replaced by its only child. This applies regardless of whether the child is a left or right child.
• A node with two children has a slightly more complicated rule: you must find the in-order successor or in-order predecessor of the node to be removed, replace the current node's value with its sucessor's or predecessor's value, then delete the successor or predecessor (according to these rules).

Answer 2

Is this homework? Nothing wrong with that... we just like to help people learn rather than tell them the answers.

If you just set the child node to null you'll lose any information about the childs children.

Answer 3

A standard tree class will know its children, usually stuck in an array or Collection - in the case of a binary tree, you've only got two direct children, so a fixed sized array will work. Because of that, they usually implement some sort of "removeMe" method that the child calls to get removed from that list of children.

As mentioned above, this gets complicated if the child you are removing has children.

Answer 4

Tim's answer seems best. But yes you will want to do one of three things depending on what kind of child it is your removing. If you make a child null, the children of it will not move up because you've lost reference to them. Instead, you'll want to determine if the left or right children of the child your removing should be set to the pointer pointing to the child your removing. After you set the previous' nodes pointer (left or right) to the child (left or right) of the node your removing, you wont have a reference anymore to that node, so theres no need to set it to null (you can't access it anymore. Unless you wrote some sort of doubly-linked BST, in which case that's not the classic BST)