Binary Search Trees

Firstly, let us make the distinction between binary trees and binary search trees. Both tree structures branch off from a root with maximum 2 children per root, but the difference is that binary search trees sort the data with a condition asserted. This is the condition that all values less than root must go on the left sub-tree of the root while all values greater than the root belongs in the right sub-tree of the root. In the basic sense, binary search trees are the sorted version of binary trees. Due to the structure of binary search trees, searching for a value in them for many of the operations such as inserting, deleting, and returning are effectively more efficient than in a simple binary tree. Because of the condition of the binary search tree, each time we look for a value in the tree, one half of the values can be ignored. For example, if we had 1,000,000 elements in the tree to search from, 500,000 would remain after the first step. This is because if the value we're looking for is larger than the one at the root, the left side is ignored because all of them is smaller than the root which means they are also smaller than the value desired. A similar argument can be said for the other case where the value is smaller than the value at the root.

Binary search trees have similar operations to binary trees, but the way they are implemented is slightly different due to the condition. When implementing methods such as adding, deleting, inserting, or returning, the first condition to check is if it is smaller, equal, or larger than the root value. Then, afterwards depending on what the method is the children are checked for the same cases recursively until the base case for the method is reached. For example, the deleting method for binary search trees have a couple of cases. They are deleting from an empty tree, deleting from a tree with either only the left child, or only the right child, and lastly deleting from the tree with both the left and right child existing. Each case effectively ignores half of tree each time recursively until the base case is reached and the objective of method is reached. The way I see it is that binary search trees are more efficient than binary trees like how binary search is more effective than linear search for large number of searches.