# Trees Notes
Algorithms Course by Grow with Google

###### tags: Data Structures & Algorithms Practice

`{%hackmd theme-dark %}`
## Tree basics
A tree starts from a place called a root and you add data to it called branches.

A *Tree* is an extension of a linked list:
* A linked list has one element at the front and a next pointer to another element and so on
* Trees as similar, the first element is called a *root*
* Instead of one next element a tree can have several
* *Node*: individual elements in a tree that contains values

* *Leaf (external nodes)*: node at the end with no children
* Parent node is an *internal node*
* *Edges*: connections to nodes, group of connections are *paths*
* *Height*: number of edges between it and the furthest leaf of a tree. The heigh of the tree overall is just the height of the root node
* *Depth:* The number of edges to the root. Hight and depth should move inversely
* *Level:* A node at a lower level is a parent and the node connected to it at a higher level is a child

## Tree Traversal
Two approaches:
1. *Depth-first* Search (DFS): If there are children nodes to explore, exploring them is the priority
* *Pre-Order*: check off a node as you see it before you travers any further in the tree. Start at root and immediately check off that we've seen it. Next, pick one of the children, normally left one and check it off too. Continue traversing through left most nodes until hitting the leafs. Check off parent and traverse to the right child and check it off too. Done with sub tree, go back to the root and do the same steps
* *In-order:*
* *Post-order:*
3. *Breadth-first* Search (BFS): The priority is visiting every node on the same level we are currently on before visiting child nodes
* *Level-Order*: Start at the root then visit its children on the second level then all of their children on the third level until you've visited every single leaf (start left then, move right)

## Search & Delete
*Binary Trees:* Trees for where parents have at most two children. Nodes can have zero, one, or two children.
* To *Search* use any traversal algorithms to go through the tree. This uses linear time search O(n) - to go through every element in the tree
* To *Delete* the operation often starts with a search to find the node you want to delete. After:
* You can delete a *leaf* and move on
* If you delete an *internal node* you'll have a gap in the tree
* If the node you want to delete has one child you can take it out move the child up and attach it to the old node's parent
* If you delete a node with two children you can:
* promote the child up just like before
* or shift the element in the deleted nodes place

### Binary Tree Practice
Now, it's your turn! Your goal is to create your own binary tree. You should start with the most basic building block:

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Every node has some value, and pointers to left and right children.

You'll need to implement two methods: `search()`, which searches for the presence of a node in the tree, and `print_tree()`, which prints out the values of tree nodes in a pre-order traversal. You should attempt to use the helper methods provided to create recursive solutions to these functions.

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree(object):
    def __init__(self, root):
        self.root = Node(root)

    def search(self, find_val):
        """Return True if the value
        is in the tree, return
        False otherwise."""
        return self.preorder_search(tree.root, find_val)

    def print_tree(self):
        """Print out all tree nodes
        as they are visited in
        a pre-order traversal."""
        return self.preorder_print(tree.root, "")[:-1]

    def preorder_search(self, start, find_val):
        """Helper method - use this to create a 
        recursive search solution."""
        if start:
            if start.value == find_val:
                return True
            else:
                return self.preorder_search(start.left, find_val) or self.preorder_search(start.right, find_val)
        return False

    def preorder_print(self, start, traversal):
        """Helper method - use this to create a 
        recursive print solution."""
        if start:
            traversal += (str(start.value) + "-")
            traversal = self.preorder_print(start.left, traversal)
            traversal = self.preorder_print(start.right, traversal)
        return traversal


# Set up tree
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)

# Test search
# Should be True
print tree.search(4)
# Should be False
print tree.search(6)

# Test print_tree
# Should be 1-2-4-5-3
print tree.print_tree()

## Binary Search Tree (BST)

BST are sorted trees - every value on the left of a particular node is smaller than it and every value on the right of a particular node is larger than it

* Unbalanced BST: The distribution of nodes is skewed to the right side
* Worst case: linear time O(n)
* Average case: O(log(n))

### BST Practice

Now try implementing a BST on your own. You'll use the same `Node` class as before:

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

This time, you'll implement `search()` and `insert()`. You should rewrite `search()` and not use your code from the last exercise so it takes advantage of BST properties. Feel free to make any helper functions you feel like you need, including the `print_tree()` function from earlier for debugging. You can assume that two nodes with the same value won't be inserted into the tree.

## Heap

In a *Heap* tree, elements are arranged in increasing or decreasing order - the root element is either the maximum or minimum value in the tree
* *Max* Heap: parent must always have a greater value that its child so the root ends up being the biggest element
* *Min* Heap: opposite - a parent has a lower value that its child so the root is the minimum element
* Heaps don't need to be binary trees, so they can have any number of children
* Heaps are often stored as arrays

## Depth-First Traversal(In order, pre order, post order) Binary Trees

class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value

 
# In Order: Left, Root, right
def inOrder(start, traversal):
    if start:
        traversal = inOrder(start.left, traversal)
        traversal += (str(start.value) + '-')
        traversal = inOrder(start.right, traversal)
    return traversal

# Preorder: Root, Left, Right
def preOrder(start, traversal):
    if start:
        traversal += (str(start.value) + '-')
        traversal = preOrder(start.left, traversal)
        traversal = preOrder(start.right, traversal)
    return traversal

# Post Order: Left, Right, Root
def postOrder(start, traversal):
    if start:
        traversal = postOrder(start.left, traversal)
        traversal = postOrder(start.right, traversal)
        traversal += (str(start.value) + '-')
    return traversal
 

# making the tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
 
# Printing the traversal results
print "In Order Traversal"
print inOrder(root, '')[:-1]
#4-2-5-1-3
print""

print "Pre Order Traversal"
print preOrder(root, '')[:-1]
#4-5-2-3-1
print""

print "Post Order Traversal"
print postOrder(root, '')[:-1]
#4-5-2-3-1

## Breadth-First(Level Order) Traversal Binary Tree
**Breadth-first search** involves search through a tree one level at a time.

We traverse through one entire level of children nodes first, before moving on to traverse through the grandchildren nodes. And we traverse through an entire level of grandchildren nodes before going on to traverse through great-grandchildren nodes

def levelOrder(root):
  if root is None:
    return
  # create empty queue to keep track of visited nodes
  queue = []
  # add / enqueue Root
  queue.append(root)
  
  #while the search queue is not empty
  while(len(queue) > 0):
    # Print front of queue and remove it from queue 
    print(queue[0].value,)
    node = queue.pop(0)
    
    #Then add the left child 
    if node.left is not None:
      queue.append(node.left)
    #Then add the right child 
    if node.right is not None:
      queue.append(node.right)
    
#making the tree 
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Level Order Traversal")
print(levelOrder(root))

For every node in our queue — always starting with the root node — we’ll want to do three things:

1. **Visit** the node, which usually just means printing out its value.
2. **Add** the node’s **left** **child** to our queue.
3. **Add** the node’s **right** **child** to our queue.

Once we do these three things, we can remove the node from our queue, because we don’t need it anymore! We basically need to keep doing this repeatedly until we get to the point where our queue is empty.

Queues follow the **first-in, first-out (FIFO) principle**, which means that whatever was enqueued first is the first item that will be read and removed from the queue.

The time complexity of a breadth-first search algorithm takes linear time, or **O(n)**, where **_n_** is the number of nodes in the tree.

[More Help](https://www.cs.bu.edu/teaching/c/tree/breadth-first/)