Binary Tree is a tree structure organized in such a way to optimize the searching for a particular node. The searching algorithm is known as binary search and has a running time of O(log2(n)) where "n" is the number of elements in the collection.
Organization[]
Binary trees are organized such that every node has 0 to 2 children nodes. Each node holds its "position" value.
The left child node holds a position value lower than the parent and the right child holds a value higher. Thus, position value of all nodes that are children of the left node are less than original parent node. Similarly all children nodes of the right node have higher value than the parent.
The parent node is chosen arbitrarily but some configurations are more optimized than others. For example, for a list of integers from 0 to 10, choosing the parent node as 10 and all subsequent nodes as the left node is not the best way to construct the tree.
Binary Search[]
The searching algorithm for a binary tree is call binary search since at every loop, the tree is cut down by half, resulting in a running time of O(log2(n)).
The algorithm is best explained with an example:
Consider a collection of 10 integers ranging from 0 to 9. The binary tree is built in the following configuration(other configurations possible):
5
/ \
3 8
/\ /\
2 4 6 9
/ \
1 7
Finding 7 will result in the following steps:
1) start from 5, 7 is larger, go to right branch.
2) 7 is smaller than 8, take the left branch.
3) 7 is larger than 6, go to the right branch.
4) 7==7, found
This algorithm took 4 steps from a collection of 10 items, proving the running time is O(log2(n)) since upperBound(log2(10)=4) This would have more dramatic effect on larger collections (running time of 1 million items is 20 steps).
Binary search works great with recursions