BINARY TREES

BINARY TREES

1. BINARY TREE

   • Hierarchical (non linear) data structure
   • General principle:
     • Node → rt/left subtree
   • Basic concepts
     • Root node → first and upper node
     • Leaves → nodes without children nodes
     • Node → object that contains an element

2. BINARY SEARCH TREE

   • Hierarchical data structure
   • Used to optimize search and data retrieving in ordered sets
   • Basic principle:
     • Left child < current node < right child
   • General principle:
     • Left subtree < root node < right subtree
   • Basic concepts:
     • Root node → first and upper node
     • Leaves → nodes without children nodes
     • Node → object that contains an element
   • steps INSERT ELEMENT in BST
     • 1. Are there elements in TREE
       • YES = begin at root
       • NO = create NEW root
     • 2. Is the new element greater than the current nodes element?
       • YES = is there a right child?
         • YES = recursively delegate to right
         • NO = new right child
       • NO = is there a left child ?
         • YES = recursively delegate to left
         • NO = new left child
   • steps SEARCH ELEMENT in BST
     • 1. Are there elements in the Tree?
       • YES = begin the process at the root
     • 2. Does the node have elements?
       • YES = return the node
       • NO = Recursively delegate
         • TO the RT, if the element we want is greater
         • OTHERWISE to the LEFT