Trees: Binary & Binary Search Trees

Overview

• Two types of trees: Binary and Binary Search
• Node: node is the individual item or data that makes up the data structure.
• Root: the first or very top node in a tree
• Left Child: node that is left of the root
• Right Child: node that is right of the root
• Edge: the link between two nodes
• Leaf: the node that does not contain either L or R child node.
• Height: tree height is determined by the number of edges from the root (“top” of the tree) to the lowest node.

Traversal

• Two ways to traverse a binary tree: Depth first or Breadth first. Use recursion to traverse tree. Use the call stack to navigate back up the tree.
• Depth first: traverses the tree via its height. Traversal method depends at which point the root is viewed Preorder: Root, L, R Inorder: L, Root, R Postorder: L, R, Root
• If “root.RightChild” or “root.LeftChild” reaches the end of a branch/leaf and can't go anywhere else, it will pop off the call stack and return to the root node.
• Breadth First: iterates through the tree by going through each level, node by node. Uses a queue to traverse the width (aka breadth) of the tree. Uses “Queue.Enqueue(root)”, which puts it in a side ways looking queue stack with our current root node on top and each L/R child under it. “Dequeue” breaks off that stack and starts on the next nodes.

Binary Trees

• Binary trees contain, at most, two children. There is no sorting order and nodes can be added if space allows.
• Can add a new node to a binary tree by filling all child spots from the top down. Once we reach the first node that does not have two child nodes, we will insert our new node as a child. Usually go from L → R. To place the node, we need to reference the newly created node and its parent node.
• BigO is always O(n), and the BigO for a node insertion using breadth first is O(w), with “w” being the largest width of the tree.
• Max width of a perfect binary tree is 2^(H-1). H = lg n

Binary Search Tree

• Type of tree that does not have structure and is organized with all values smaller than our root placed to the left. Values larger than our root placed right.
• Search is much faster as we just compare our search to each root.
• BST search is best done using a “while” loop w/ a condition to keep running till it hits a leaf or target.
• BigO for insertion and search is O(log n), meaning we can reduce the number of searches performed of a logarithmic value each iteration. BigO space is O(1) as no added space is needed.