Trees

When thinking about trees, think recursion. Trees are a type of graph where child nodes consist of their own subtrees. Trees have a root node at the top. The edges of a tree are typically directional towards a node's children, and are acyclic. Each child node can only have one parent. The space complexity of trees are O(n) because you have n nodes and constant edges based on n.

Binary Tree

Each node in a binary tree has at most 2 children. Many operations on a binary tree have logarithmic time complexity. K-ary trees is a way of describing trees where nodes have at most k children.

Types of Binary Trees

Perfect Binary Trees are where all the interior nodes have two children, and the leaf (bottom) nodes have the same depth.

Complete Binary Trees are where all interior nodes have two children, but the leaf nodes aren't all at the same depth. Essentially, the bottom level is not fully filled, however it must be filled from left to right.

Balanced Binary Trees are where all left and right subtrees depth differs by no more than 1. This is what allows trees to have a O(log(n)) search complexity.

Full Binary Trees are where all child nodes have either zero or two child nodes. No child nodes have only one child.

Binary Search Tree

A binary search tree or BST is a tree where the left child node is always less than the parent, and the right child node is always greater. This allows for very fast searching since it is easy to make a decision on which path to check down next.

Searching

There are two main methods for searching trees: Breadth First Search and Depth First Search. In BFS, we traverse the tree level by level, and in DFS we traverse sub-tree by sub-tree, going down to the bottom and working our way up. BFS uses a queue (FIFO) and DFS uses a stack (LIFO). Within DFS we can traverse in order (Left-Root-Right), preorder (Root-Left-Right), or postorder (Left-Right-Root).

def BFS(root):
    if root is None:
        return

    queue = [root]

    while queue:
        node = queue.pop()  # dequeue a node from the front of the queue
        print(node.value, end=' ')  # visit the node (print its value in this case)

        # Can also be done with n children if not binary tree
        # enqueue left child
        if node.left:
            queue.append(node.left)
        # enqueue right child
        if node.right:
            queue.append(node.right)

def DFS(node):
    if node is None:
        return

    # This example is pre-order, but just rearrange the order in which you check to make it in-order or post-order
    # Visit the node (print its value in this case)
    print(node.value, end=' ')
    # Recursively call DFS on the left child
    DFS(node.left)
    # Recursively call DFS on the right child
    DFS(node.right)