Breadth First Search And Depth First Search

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

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);

no, it was for teaching purposes only