Depth First Search

depth_first_search.js

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

//Time Complexity: O(N) since we traverse every node worst case
//Space Complexity: O(H) height of tree is number of stack frames in memory
const dfs = (node, value) => {

  if(!node) {
    return;
  }
  
  if(node.value === value) {
    return node;
  }
  
  let n;
  n = dfs(node.left, value);
  if(n) {
    return n;
  }
  n = dfs(node.right, value);
  if(n) {
    return n;
  }
}

let a = new Node('a');
let b = new Node('b');
let c = new Node('c');
let d = new Node('d');
let e = new Node('e');
let f = new Node('f');
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;

console.log(dfs(a, 'd'))