to as shown in figure the data items in node are arranged in ascending key orderby convention from left to right (lower to higher numbersan important aspect of any tree' structure is the relationship of its links to the key values of its data items in binary treeall children with keys less than the node' key are in subtree rooted in the node' left childand all children with keys larger than or equal to the node' key are rooted in the node' right child in tree the principle is the samebut there' more to itall children in the subtree rooted at child have key values less than key all children in the subtree rooted at child have key values greater than key but less than key all children in the subtree rooted at child have key values greater than key but less than key all children in the subtree rooted at child have key values greater than key this is shown in figure duplicate values are not usually permitted in treesso we don' need to worry about comparing equal keys figure keys and children refer to the tree in figure as in all treesthe leaves are all on the same level (the bottom rowupper-level nodes are often not fullthat isthey may contain only one or two data items instead of three alsonotice that the tree is balanced it retains its balance even if you insert sequence of data in ascending (or descendingorder the tree' self-balancing capability results from the way new data items are insertedas we'll see in moment searching finding data item with particular key is similar to the search routine in binary tree you start at the rootandunless the search key is found thereselect the link that leads to the subtree with the appropriate range of values for exampleto search for the data item with key in the tree in figure you start at the root you search the rootbut don' find the item because is larger than you go to child which we will represent as (remember that child is on the rightbecause the numbering of children and links starts at on the left you don' find the data item in this node eitherso you must go to the next child herebecause is greater than but less than you go again to child this time you find the specified item in the link insertion new data items are always inserted in leaveswhich are on the bottom row of the tree if