Pacific-Design.com

    
Home Index

1. Binary Search Tree

+ 1 Breadth First Search

+ 2 Depth First Search

+ Code

+ Traversal

Binary Search Tree /

Binary Search Tree = O(log n)

       Average     Worst case
Space   O(n)        O(n)
Search  O(log n)    O(n)
Insert  O(log n)    O(n)
Delete  O(log n)    O(n)

Node Class

public class Node<T> {

  public int value;
  public Node left;
  public Node right;

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

}

Find Minimum Value

public int findMinimum(){

  if ( root == null ) return 0;
  Node node = root;

  while(node.left != null){
    node = node.left;
  }

  return node.value;
}

Find Maximum Value

public int findMaximum(){

  if ( root == null ) return 0;
  Node node = root;

  while(node.right != null){
    node = node.right;
  }

  return node.value;
}

Inoder Traversal - Sorted Order

3, 10, 17, 25, 30, 32, 38, 40, 50, 78, 78, 93.
public void InOrder(){
  traversal(root);
  System.out.println("");
}

private void traversal(Node node){
  if ( node == null ) return;

  traversal(node.left);
  System.out.print(node.value+", ");
  traversal(node.right);
}

Preorder Traversal


40, 25, 10, 3, 17, 32, 30, 38, 78, 50, 78, 93.
public void PreOrder() {
  traversal(root);
  System.out.println("");
}

private void traversal(Node node) {
  if (node == null) return;

  System.out.print(node.value + ", ");
  traversal(node.left);
  traversal(node.right);
}

Postorder Traversal


3, 17, 10, 30, 38, 32, 25, 50, 93, 78, 78, 40.
public void PostOrder() {
  traversal(root);
  System.out.println("");
}

private void traversal(Node node) {
  if (node == null) return;

  traversal(node.left);
  traversal(node.right);
  System.out.print(node.value + ", ");

}

Breadth First Search

public class BreadthFirstSearch {

    public void search(Node root) {

        Queue queue = new Queue();                  // create a queue
        visit(root);                                // get root children
        root.visited = true;
        queue.enqueue(root);                        // add node to the queue

        while(!queue.isEmpty()) {

            Node parent = queue.dequeue();          // remove node from the queue

            foreach(Node node in parent.adjacent) { // iterate through each adjacent parent node

                if(node.visited == false) {         // visit node if was not visited
                    visit(node);
                    node.visited = true;
                    queue.enqueue(node);            // remove node from the queue
                }
            }
        }
    }
}

Depth First Search

public class DepthFirstSearch {

    public void search(Node root) {

        if(root == null) return;
        visit(root);
        root.visited = true;

        foreach(Node node in root.adjacent) {
            if(node.visited == false) {
                search(node);
            }
        }
    }
}

References:


Trees

Binary Search Tree: O(log n)

Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search
https://en.wikipedia.org/wiki/Binary_search_tree

Breadth First Search - O(V+E) vertex + edge

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.
https://en.wikipedia.org/wiki/Breadth-first_search

References: