Binary Search Tree

Binary Search Tree

1. Hierarchical (non-linear) data structure

   • Used to optimize data retrieval in ordered sets of numbers
     • Node
       • Left child (smaller than node)
       • Right child (greater than node)
     • Basic principle: left child < current node < right child
     • General principle: left subtree < root node < right subtree

2. Basic Concepts

   • Root Node - first and uppermost node
   • Leaves - Nodes without children Nodes
   • Node - Object that contains an element

3. Inserting Elements

   • Are there any elements in the BST?
     • No - Create a root node with the new element!
     • Yes!
       • Is the new element smaller, equal, or greater than the current node?
         • Smaller
           • Is there a left child of the current node?
             • No - Create a node with the new element as the left child of the current node!
             • Yes - Compare new element to the left child!
         • Greater
           • Is there a right child of the current node?
             • No - Create a node with the new element as the right child of the current node!
             • Yes - Compare new element to the right child!
         • If it is equal to the node, then you do not need to create a new node!

4. Searching for Elements

   • Are there any elements in the BST?
     • No - The element cannot exist in the BST.
     • Yes!
       • Is the element you're search for smaller, equal, or greater than the current node?
         • If it is equal to the node, then you have found the element!
         • Smaller
           • Is there a left child of the current node?
             • Yes - Compare element to the left child!
             • No - The element does not exist in the BST.
         • Greater
           • Is there a right child of the current node?
             • Yes - Compare element to the right child!
             • No - The element does not exist in the BST.