Binary Trees

Binary Trees

1. Binary Tree

   • Hierarchical data structure
     • Each node has a left and a right subtree
   • Parts of the binary tree
     • Root node
       • The first and upper Node
     • Leaves
       • Nodes without children Nodes
     • Node
       • An Object that contains an Element

2. Binary Search Tree

   • Hierarchical data structure
     • Used to optimize search and data retrieving in ordered sets
   • Search organization
     • Left child < current Node < right child
     • Left subtree < root Node < right subtree
   • Adding an element to the BST
     • 1) Check if there are elements already in the Tree
       • If there are, begin the process at the Root
       • If there are not, create a new Root
     • 2) Check if the new element is greater than the current Node's element
       • If it is, check to see if there's a right child, and either delegate the new element to the right, or create a new right child
       • If it's not, either delegate the new element to the left, or create a new left child
   • Searching for an element in the BST
     • 1) Check if there are elements in the tree, and if there are, begin the process at the Root
     • 2) Check if the current Node has the element
       • If it does, return the Node
       • If it doesn't, recursively delegate to the right if we want a greater element, and to the left if we want a lesser element
   • Creating a basic BST in Python
     • We will have a Tree class, which includes a variable for the number of elements. It has a constructor, an insert function, and a search function.
     • We will have a Node class, which is considered to be a subclass of the Tree class. Each Node has a left and right child. Nodes have a variable for an element, along with a constructor, a function to insert an element, and a function to search for an element.