trees-n-graphs-notes.md

Tree

• a datastructure composed of nodes
• each tree has a root node
• the root node has zero or more child nodes
• each child node has zero or more child nodes, and so on.
• a tree cannot contain cycles
• the nodes may or may not be in a particular order
• the nodes can have any datatype as values
• the nodes may or may not have links back to their parent nodes

A simple class definition of Node:

class Node {
  public String name;
  public Node[] children;
}

You might also have a Tree class to wrap this node:

class Tree {
  public Node root;
}

Binary Tree

• a tree in which each node has up to two children
• not all trees are binary trees
• a node is called a "leaf" node if it has no children

Binary Search Tree

• a binary tree in which every node fits a specific ordering property:
  • all left descendents <= n < all right descendents

Balanced Tree

• balanced enough to ensure O(log n times) for insert and find, but it's not necessarily balance as it should be.
• common types include: red-black trees and AVL trees

Complete binary trees

• a binary tree in which every level of the tree is fully filled, except for perhaps the last level.
• to the extent that the last level is filled, it is filled left to right

Full Binary Trees

• a binary tree in which every node has either zero or two children

Perfect Binary Trees

• a binary tree in which it is both full and complete
• all leaf nodes will be at the same level, and this level has the maximum number of nodes

Binary Tree Traversal

• In-Order Traversal
  • means to visit the left branch then the current node, then right branch
  • when performed on a binary search tree, it visits nodes in ascending order
• Pre-Order Traversal
  • visits the current node before its child nodes
  • the root is always the first node visited
• Post-Order Traversal
  • visits the current node after its child nodes
  • the root is always the last node visited

Binary Heaps

• a complete binary tree

Tries (Prefix Trees)

• a trie is a variant of an n-arry tree in which characters are stored at each node

Graphs

• a type of tree, but not all graphs are trees because a tree is a connected graph without cycles
• a graph is a collection of nodes with edges between them
• graphs can be either directed (one way) or undirected (two way)
• a graph might consist of multiple isolated graphs. if there is a path between every pair of vertices, it called a "connected graph"
• a graph can have cycles
• an "acyclic graph" is one without cycles

Adjacency List

• it is the most common way to represent a graph

class Graph {
  public Node[] nodes;
}

class Node {
  public String name;
  public Node[] children;
}

Adjacency Matrices

• an NxN boolean matrix, where a true value at matrix[i][j] indicates an edge from node i to node j
• in an undirected graph, an adjacency matrix will be symmetric.
• in a directed graph, a adjacency matrix will be not

Depth-First Search (DFS)

• we start at the root and explore each branch completely before moving on to the next branch
• we go deep first before going wide

void search(Node root) {
  if (root == null) return;
  visit(root);
  root.visited = true;
  for each (Node n in root.adjacent) {
    if (n.visited == false) {
      search(n);
    }
  }
}

Breadth-First Search (BFS)

• we start at the root and explore each neighbor before going on to any of their children.
• we go wide before going deep

void search(Node root) {
  Queue queue = new Queue();
  root.marked = true;
  queue.enqueue(root);
  
  while (!queue.isEmpty()) {
    Node r = queue.dequeue();
    visit(r);
    for each (Node n in r.adjacent) {
      if (n.marked == false) {
        n.marked = true;
        queue.enqueue(n);
      }
    }
  }
}

Bidirectional Search

• used to find the shortest path between a source and destination node.
• it operates by essentially running two simultaneous BFS, one from each node
• when their searches collide we have found a path