Search in Binary Search Tree L:

  1. Compare X to the root (i.e. middle value) (M) in L.
  2. if X = M we are done.
  3. if X < M we recursively search for X in L's left subtree.
  4. if X > M we recursively search for X in L's right subtree.

Example: search for 5 in earlier tree.

It is easy to traverse a BST in increasing order. From the node containing the value N

  1. process all values smaller than N - i.e. traverse N's left subtree.
  2. process N itself.
  3. process all values bigger than N - i.e. traverse N's right subtree.
This is left-to-right infix traversal.

How to traverse a BST in decreasing order?

Answer: right-to-left infix traversal.