Binary Trees

Binary Trees

1. The Binary Tree

   • What is it?
     • Nonlinear data structure
     • Hierarchal in nature
   • What are the elements?
     • Root: the first and uppermost node
     • Leaves: the nodes without children nodes
     • Nodes: objects that contain an element
   • How is it organized?
     • Elements can be ordered but do not have to be
     • Repeated elements are allowed
   • 1
     • 5
       • 6
         • 9
       • 2
     • 8
       • 2
         • 3
         • 7
       • 4

2. The Binary Search Tree

   • What is it?
     • Nonlinear data structure
     • Hierarchal in nature
   • What are the elements?
     • Root: the first and uppermost nod
     • Leaves: the nodes without children nodes
     • Nodes: objects that contain an element
   • How is it organized?
     • Elements are ordered
       • Repeated elements are not allowed
     • Left subtree < current node < right subtree
   • 5
     • 4
       • 3
     • 9
       • 8
       • 11
         • 10
   • Adding elements to the Binary Search Tree
     • First ask: Are there elements in the tree already?
       • If yes: Begin going through the tree starting at the root
         • Then ask: Is the new node's element greater than the current node's element?
           • If yes
             • Ask: Is there already a right subtree?
               • If yes: recursively check through and compare the remaining elements
               • If no: create a new right subtree
           • If no
             • Ask: Is there already a left subtree?
               • If yes: recursively check through and compare the remaining elements
               • If no: create a new left subtree
       • If no: Create a root by adding an element to the tree
   • Searching for elementts in the Binary Search Tree
     • First ask: Are there elements in the tree already?
       • If yes: Begin checking at the root node
         • Then ask: Does the node have the element we are searching for?
           • If yes: Return that node
           • If no: Recursively check
             • Is the search element less than the current node?
               • If yes: recursively check to the left subtree
               • If no: recursively check to the right subtree
       • If no: The element is not in the tree because there are no elements in the tree