Trees

Trees

A tree is made up of nodes (data elements) with zero, one or several references to other nodes. Each node has only one other node referencing it.

• Parent - a node that points other nodes; Every node except the root has one parent
• Child - a node is the child of any node that points to it
• Descendant - all the nodes that can be reached by following a path of child nodes from a particular node
• Ancestor - any other node for which the node is a descendant
• Leaves - nodes that do not have a child

Binary Trees

A binary tree is a special type of tree in which each has no more than two children (left and right)

// simple implementation
public class Node {
    public Node Left {get;}
    public Node Right {get;}
    public int Value {get;}
    public Node (Node left, Node right, int value) {
        Left = left;
        Right = right;
        Value = value;
    }
}

Binary Search Trees

Trees are often used to store sorted or ordered data. The most common way to store ordered data in a tree is to use a special treed called a Binary search Tree(BST). In a BST, the value held by a nod’s left child is less than or equal to its own value, and the value held by a nod’s right child is greater than or equal to its value.

Lookup, Deletion, Insertion are O(log(n)) operations

Smallest element can be obtained by following all the left children; largest by following the right children

// simple lookup
public Node FindNode (Node root, int value) {
	while (root != null) {
        int currVal = root.Value; 
        if (currVal == value) 
            break;
        if (currVal < value) 
            root = root.Right;
        if (currVal > value)
            root = root.Left;
    }
    return root; 
}

// recursive 
public Node FindNode(Node root, int value) {
    if (root == null) {
        return null; 
    }
    //base case
    if (root.Value == value) {
        return root; 
    } else if (root.Value < value) {
        return FindNode(root.Right, value);
    } else if (root.Value > Value){
        return FindNode(root.Left, value);
    } else {
        //should never get here
    }
}

Heaps

Heaps are trees where (in a max-heap) each child of a node has a value less than or equal to the node’s own value. Because of this, the largest and smallest values can be found in constant time in heaps.

Common Searches

• Breadth first search - start with the root, and move left to right across each level till all nodes have been examined or find the node that you searching for.
  • Con - requires additional memory as it needs to track all child nodes for all nodes on a given level
• Depth First Search - start with the root, and follows the branch as many level as possible until the target node is found or the end is reached. When the search can’t go down any farther, it is continued at the nearest ancestor with unexplored children

Traversals

• Preorder: Node –> Left descendants –> Right descendants
• Inorder : Left descendants –> Node –> Right descendants
• Postorder: Left descendants –> Right descendants –> Node

Graphs

Graphs more general and complex. Graph nodes (vertices) can have multiple parents. Links between nodes (edges) contain more information than just a simple reference/pointer.

• Directed Graph: a graph with one-way edges
• Undirected Graph: a graph with two-way edges

Common Representations

• Adjacency List: a list of references to other nodes with which the node shares edges
• Adjacency Matrix: a square matrix with dimension equal to the number of nodes where matrix element (i,j) represents the number of edges extending from node i to node j