 right|200px|thumb|a binary search tree of size 9 and depth 3, with root 8 and leaves 1, 4, 7 and 13 in computer science, a binary search tree (bst), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure where each node has a comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left sub-tree are smaller than the keys in all nodes in that node's right sub-tree. each node has no more than two child nodes. each child must either be a leaf node or the root of another binary search tree. the left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node. bsts are also dynamic data structures, and the size of a bst is only limited by the amount of free memory in the operating system. the main advantage of binary search trees is that it remains ordered, which provides quicker search times than many other data structures. the common properties of binary search trees are as follows: * the left subtree of a node contains only nodes with keys less than the node's key. * the right subtree of a node contains only nodes with keys greater than the node's key. * the left and right subtree each must also be a binary search tree. * each node can have up to two successor nodes. * there must be no duplicate nodes. * a unique path exists from the root to every other node. generally, the information represented by each node is a record rather than a single data element. however, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records. the major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient. the other advantages are: * binary search tree is fast in insertion and deletion etc. when balanced. * very efficient and its code is easier than other data structures. * stores keys in the nodes in a way that searching, insertion and deletion can be done efficiently. * implementation is very simple in binary search trees. * nodes in tree are dynamic in nature. binary search trees are a fundam
Binary_trees Data_types Search_trees