bertoort/bfs_and_dfs.md

## bfs_and_dfs.md

      
    Raw
  

              bfs_and_dfs.md
            
          
    Breadth First Search

Algorithm for searching graph-like data structures, one level at a time.

Step by Step


Start a queue
Check current node - if false, mark as visited, continue
Add all unvisited, connected nodes to queue
Check one by one like the previous node and repeat


JS Example

function bfs(value, node) {

  let ticks = 0;

  queue = [];

  queue.unshift(node);

  while (queue.length > 0) {
    ticks++
    curNode = queue.pop();
    if (curNode.value === value) {
      return {node: curNode, ticks};
    }

    let len = curNode.children.length;

    for (let i = 0; i < len; i++) {
      queue.unshift(curNode.children[i]);
    }
  }
  
  return {node: null, ticks}
}

Complexity

O(n^2)

When to Use


Solution is not far from the root of the tree
Tree is very deep and solutions are rare


Depth First Search

Algorithm for searching graph-like data structures... aggresively.

Step by Step


Check current node - if found, return node
For that node find the length of children
For that length, recursively repeat search


JS Examples


Example One

function dfs(value, node) {

  if (node.value === value) {
    return node;
  }

  var len = node.children.length;

  for (var i = 0; i < len; i++) {
    var foundNode = dfs(value, node.children[i]);
    if (foundNode) {
      return foundNode;
    }
  }
  return null;
}

Example Two

function dfs(value, node) {
  let ticks = 0;

  stack = [];

  stack.push(node);

  while (stack.length !== 0) {
    ticks++;
    let curNode = stack.pop();
    if (curNode.value == value) {
      return {node: curNode, ticks};
    }
    
    let len = curNode.children.length;

    for (let i = 0; i < len; i++) {
      stack.push(curNode.children[i]);
    }  
  }
  
  return {node: null, ticks}
}

Complexity

O(n^2)


Much lower memory requirements (compared to BFS)
Common, usually far from root


## bts_and_examples.md

      
    Raw
  

              bts_and_examples.md
            
          
    BST

function BSTNode(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

BSTNode.prototype.add = function (node) {
  if (node.value < this.value) {
    this.left ? this.left.add(node) : this.left = node;
  } else {
    this.right ? this.right.add(node) : this.right = node;
  }
}
Example

let bstn1 = new BSTNode(8);
let bstn2 = new BSTNode(3);
let bstn3 = new BSTNode(1);
let bstn4 = new BSTNode(6);
let bstn5 = new BSTNode(4);
let bstn6 = new BSTNode(7);
let bstn7 = new BSTNode(10);
let bstn8 = new BSTNode(14);
let bstn9 = new BSTNode(13);

for (let i = 2; i < 10; i++) {
  bstn1.add(window[`bstn${i}`]);
}
BST Search Algo

function search(node, value) {
  let ticks = 1;
  let curNode = node;
  while(curNode.value !== value) {
    ticks++
    if (curNode.value < value) {
      curNode = curNode.right;
    } else {
      curNode = curNode.left;
    }
  }
  return {node: curNode, ticks}
}
Simple Tree Example

function Node(value) {
  this.value = value;
  this.children = [];
}

Node.prototype.add = function (node) {
  this.children.push(node);
}

let n1 = new Node(3);
let n2 = new Node(62);
let n3 = new Node(43);
let n4 = new Node(22);
let n5 = new Node(2);
let n6 = new Node(88);
let n7 = new Node(64);
let n8 = new Node(24);
let n9 = new Node(5);
let n10 = new Node(71);

n1.add(n2);
n1.add(n3);
n3.add(n4);
n3.add(n10);
n4.add(n5);
n2.add(n6);
n4.add(n7);
n4.add(n8);
n8.add(n9);