Binary Trees (Lecture)

Binary Trees (Lecture)

1. Basics

   • Root node is the first and upper node
   • Node: object that contains an Element
   • Leaves: Nodes without children
   • Hierarchical data structure

2. Binary Search Tree(BST)

   • Basic Principle: Left Child < Current Node < Right Child
   • Can be used to optimize search and data retrieving in ordered sets
   • Inserting elements into BST
     • If element is empty, first inserted item becomes root
     • If the new element is larger than the current Node. Check for a right child.
       • If there is a right child, repeat the process with that node, if not, the new element becomes the right child
     • If the new element is less than the current Node. Check for a left child.
       • If there is a left child, repeat the process with that node, if not, the new element becomes the left child
   • Searching for element in BST
     • Begin with root
     • Does the current node have the element we are searching for?
       • Yes? Return the node
       • No? Delegate to the right if the search element is greater than the current element. Otherwise, delegate left.