Binary trees
adding and deleting nodes
A Binary Tree - sometimes called a Binary Search Tree - is composed of Nodes.
Each node stores an item of data and a pointer to its left and right child.
A node which does not have any children is called a leaf node.
To get an insight of how to add and delete a node from a binary tree, watch this great video.
Video Review
Deleting leaf node
Starting at the root node, search for the node to be deleted and store a reference to the parent node.
Once the node to be deleted has been found, simply set the correct pointer in the parent to be null.
Delete a node with one child
Starting at the root node, search for the node to be deleted and store a reference to the parent node.
Once the node to be deleted has been found, simply set the correct pointer in the parent to be the same as the pointer to the deleted node's child.
Deleting a node with two children
Starting at the root node, search for the node to be deleted.
Then, find the greatest value in the left subtree of the node to be deleted (or the least value in the right subtree)
Replace the data in the node to be deleted with this greatest value (or least value if evaulating the right subtree).
Finally, delete the node which has the least value in the left subtree of the node to be deleted (or otherwise if evaluating the right subtree!)
Note: when deleting the node in the with the least value, make sure you determine if it is a leaf node, a node with one child, or a node with 2 children and adopt an appropriate strategy.
Click the exercises button and attempt the questions.