Binary Search Tree
A binary search tree is a node-based data structure that stores data according to a set of rules. The left subtree of any node will have a value less than the parent node's value. The right subtree of any node will have a value greater than the parent node’s value. The left and right subtrees must be a binary search tree.
The nodes for a binary tree will have 3 types of data. The first type is the value stored in the node. The other two are pointers to the left and right nodes.
Searching a binary search tree works similarly to a binary search. The values are ordered so that each search will eliminate half of the possible options.
Let's look for 1 in the binary search tree shown above.
First, you will determine that 1 is less than the root 5 and so it must be to the left.
Next, you will determine that 1 is less than 3. This will allow you to continue searching only the left options.
Next, you will determine that 1 is less than 2. You will continue searching left.
Finally, you will determine that l is in the search tree.
Here is a code example of how to implement searching the tree.
To insert into a binary tree you will search through the tree until you find the correct position the value should go. This works by comparing the value of a node to the value you want to insert. If the root is null you will add the value that you want to insert into that null value. If the value is not null, you will go to the left or right depending on whether the value you want to insert is less than or greater than the value of the root.
Here is a code implementation of insertion.
When deleting a value you will have three possible scenarios.
The first is when the value you want to delete has no children. In this case, just delete the value.
The second case is when the value has one child. In this case, copy the child to the parent and delete the child.
The last case is when the value has two children. In this case, find the inorder successor. Then copy the inorder successor's value to the value you are deleting and then delete the inorder successor.
Here is a code implementation of deletion.