efficient binary trees learning objective in this we will discuss efficient binary trees such as binary search treesavl treesthreaded binary treesred-black treesand splay trees this is an extension of binary trees binary search trees we have already discussed binary trees in the previous binary search treealso known as an ordered binary treeis variant of binary trees in which the nodes are arranged in an order in binary search treeall the nodes in the left sub-tree have value less than that of the root node correspondinglyall the nodes in the right sub-tree have value either equal to or greater than the root node the same rule is applicable to every sub-tree in the tree (note that binary search tree may or may not contain duplicate valuesdepending on its implementation look at fig the root node is the left sub-tree of the root node consists of nodes and all these nodes have smaller values than the root node the right sub-tree of the root node consists of nodes and recursivelyeach of the sub-trees also obeys the binary search tree constraint for examplein the left sub-tree of the root node is the root and all elements in its left sub-tree ( are smaller than while all nodes in its right sub-tree ( and are greater than the root node' value since the nodes in binary search tree are orderedthe time needed to search an element in the tree is greatly reduced whenever we search for an elementwe do not figure binary search tree