search tree

A search tree is a tree where every subtree of a node has keysless than any other subtree of the node to its right. The keys in a node areconceptually between subtrees and are greater than any keys in subtrees to itsleft and less than any keys in subtrees to its right.

A search might visit nodes in the tree to locate some information. At the outset ofthe search one has a given key and seeks to find the node in the tree having that key.As the nodes are visited a comparison of the node’s key to the given key is madeand a decision to go to either the left subtree or the right subtree is made.Knowing that all keys to the left (right) are smaller (larger) makesthe search easy to carry out.