Trees/Removal

Removing single node from unsorted tree

Removal operation for trees:

• One way to call the remove() method is with no parameters
• This replaces a node with its child
• Raises an exception if a node has two (or more) children

Removing single node from sorted tree

But it also gets more complicated.

• In a sorted binary tree, need to rearrange the tree - traverse the tree to find the preceding node, and replace the node being removed with the preceding node.
• This requires traversing potentially the entire height of the tree, and so costs O(log N).

Removing subtree from unsorted tree

Removing a subtree:

• Removal of an entire subtree should be possible.
• Pass in a position in the tree, the method will remove the node at that position, as well as any child nodes.
• This is done by first setting the left and right children of the target position to null, then finding the parent of the target and setting its child equal to null.
• In a tree these are the only possible nodes that could point to this node.

Removing subtree from sorted tree

Removing a subtree from a sorted tree:

• When removing a subtree in a sorted tree, you're removing a set of contiguous values.
• No need to balance tree, because no possible child nodes needing reordering.