A binary search tree is a data structure that is highly efficient at storing data. From the root node, it has two main nodes. The important point to note here is that the nodes in the left sub-tree have fewer values than the root node, and the nodes on the right of the root node have proportionately greater values than the root. Furthermore, at any one time, both the left and right sub-trees constitute their own binary search trees.
Binary search tree in data structure is a type of tree having either 0/1/2 nodes.
It has following characterstics:
-
Root node is less than right node but greater than left node.
-
To find a element in tree max comparison needed = hight of tree
-
Time complexity for search= O(n)
For example, to search for 16, we first note that 16 < 20 and we traverse to the left child. The second comparison finds that 16 > 7, so we traverse to the right child.Each comparison results in reducing the number of items to inspect by one-half. In this respect, the algorithm is similar to a binary search on an array. However, this is true only if the tree is balanced.