chap binary trees (aposition parent left child right child left sibling right sibling (bfigure complete binary tree and its array implementation (athe complete binary tree with twelve nodes each node has been labeled with its position in the tree (bthe positions for the relatives of each node dash indicates that the relative does not exist array-based list to implement the dictionarythen binary search can be used to find record in only th(log ntime howeverinsertion will now require th(ntime on average becauseonce the proper location for the new record in the sorted list has been foundmany records might be shifted to make room for the new record is there some way to organize collection of records so that inserting records and searching for records can both be done quicklythis section presents the binary search tree (bst)which allows an improved solution to this problem bst is binary tree that conforms to the following conditionknown as the binary search tree propertyall nodes stored in the left subtree of node whose key value is have key values less than all nodes stored in the right subtree of node whose key value is have key values greater than or equal to figure shows two bsts for collection of values one consequence of the binary search tree property is that if the bst nodes are printed using an inorder traversal (see section )the resulting enumeration will be in sorted order from lowest to highest