Terminology

• Trees
  • A data structure with a root node and children
  • A node can have any number of children (0 to N), but every node can have only one parent!
    • This is what separates a tree from a graph: if a node has 2 parents, it is no longer a tree but it's a graph
  • There is no strictly required ordering of data
  • An example: A linkedlist is a tree that doesn't fork
• Binary Tree
  • A specific type of tree that can have at most 2 children (left and right)
  • There is still no required ordering of the values
• Binary Search Tree (BST)
  • A specific type of binary tree
  • Must satisfy the binary tree rule (max 2 children) AND a specific sorting rule
  • The BST property
    • Everything in the left subtree is smaller than the parent
    • Everything in the right subtree is larger than the parent
  • Purpose is for fast searching - Because of the sorting, you can cut the search space in half every step (binary search)

Types of binary trees

• Full Binary Tree
  • Every node has either 0 or 2 children.

      1              1
     / \            / \
    2   3          2   3
   / \            /
  4   5          4
  (Full)      (Not Full - Node 2 has 1 child)

• Perfect Binary Tree

  • All internal nodes have 2 children, and all leaf nodes are at the exact same level. (The triangle is perfectly filled)

  • Any level in the tree that has any nodes is completely filled all the way across

       1                 1
     /   \             /   \
    2     3           2     3
   / \   / \         / \    /
  4   5 6   7       4   5  6
 (Perfect)         (Not Perfect)
 (Last level       (Last level
  filled)          not filled)

• Complete Binary Tree
  • It must have all levels filled completely, except possibly the last level
    • Crucially, the nodes in the last level must be filled from left to right
  • A perfect tree is also complete

       1                 1
     /   \             /   \
    2     3           2     3
   / \   /           / \     \
  4   5 6           4   5     7
 (Complete)       (Not Complete)
 (Last level       (Node 7 exists, but
  filled L->R)      Node 6 is missing)

Balanced VS Unbalanced Trees

"Balanced" refers only to the shape (height) of the tree & not the values inside.

• Balanced Tree
  • The left and right subtrees of any node differ in height by at most 1
  • Guarantees that search/insert/delete operations take O(log n) time
  • Examples: AVL Trees, Red-Black Trees (these algorithms automatically rearrange nodes to keep the tree balanced)
• Unbalanced Tree
  • The tree leans heavily to one side
  • A Degenerate Tree (or Pathological Tree) is a tree where every parent has only one child -> It essentially becomes a Linked List
  • Searching becomes O(n) (slow), effectively losing the advantage of using a tree

Depth, Height, and Big O

• Depth (Level)
  • Measures how far a node is down from the root (depth 0)
  • We count edges downwards
• Height
  • Measures how far a node is up from the deepest leaf (height 0)
  • The "height of the tree" refers to the height of the root node

        (Root)
          A           <-- Depth: 0 | Height: 2
        /   \
       B     C        <-- Depth: 1 | Height: 1
      / \     \
     D   E     F      <-- Depth: 2 | Height: 0

In a Perfect Binary Tree, every time we go down one level (depth), the number of nodes we can hold doubles:

Depth 0:       O            (2^0 = 1 node)
             /   \
Depth 1:    O     O         (2^1 = 2 nodes)
           / \   / \
Depth 2:  O   O O   O       (2^2 = 4 nodes)

Total Nodes (n) = 7
Height (h) = 2

• Formulas
  • Total nodes = $n = 2^{h+1} - 1$
    • So roughly, total nodes is close to $2^h$, or $n \approx 2^h$
  • Nodes at last level: $n = 2^h$
  • $h \approx \text{log}_2(n)$
    • $h$: height of tree
    • $n$: number of total nodes
• Big O analysis
  • Best case: Balanced Tree
    • $h \approx \log_{2}n$
    • Complexity: $O(\log n)$
    • The search speed is very fast because every step we cut the search speed in half
  • Worst case: Unbalanced / Degenerate Tree
    • $h \approx n$
    • Complexity: $O(n)$
    • The search speed is very slow because we can't cut the search space in half but have to search through every node.

Algorithms

BFS

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
    }
}

public ArrayList<Integer> BFS() {
    Node cur = root;
    Queue<Node> queue = new LinkedList<>();
    ArrayList<Integer> results = new ArrayList<>();

    // if tree is empty, return empty list
    if (cur == null) return results;

    queue.add(cur);

    while (!queue.isEmpty()) {
        Node curNode = queue.remove();
        results.add(curNode.value);
        if (curNode.left != null) queue.add(curNode.left);
        if (curNode.right != null) queue.add(curNode.right);
    }
    return results;
}

DFS

Three different ways in doing DFS

It helps if you see the order of the root!

Next, these are code to print out the nodes' values in the following orders, storing the results in a results arraylist (in Java).

PreOrder

• Root -> Left -> Right

public ArrayList<Integer> DFSPreOrder() {
    ArrayList<Integer> results = new ArrayList<>();

    class Traverse {
        Traverse(Node cur) {
            results.add(cur.value); // here
            if (cur.left != null) new Traverse(cur.left);
            if (cur.right != null) new Traverse(cur.right);
        }
    }

    new Traverse(root);
    return results;
}

InOrder

• Left -> Root -> Right
• Look at the name "inorder" -> the results will be in order!

public ArrayList<Integer> DFSPreOrder() {
    ArrayList<Integer> results = new ArrayList<>();

    class Traverse {
        Traverse(Node cur) {
            if (cur.left != null) new Traverse(cur.left);
            results.add(cur.value); // here
            if (cur.right != null) new Traverse(cur.right);
        }
    }

    new Traverse(root);
    return results;
}

PostOrder

• Left -> Right -> Root

public ArrayList<Integer> DFSPreOrder() {
    ArrayList<Integer> results = new ArrayList<>();

    class Traverse {
        Traverse(Node cur) {
            if (cur.left != null) new Traverse(cur.left);
            if (cur.right != null) new Traverse(cur.right);
            results.add(cur.value); // here
        }
    }

    new Traverse(root);
    return results;
}