binary-tree.md

Binary Tree

Tree Nodes

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

Tree Traversal

BFS

implement a queue

DFS

implement a stack

Pre-order

node,l. subtree, r. subtree

In-order

l.subtree, node, r.subtreethe left subtree contains values less than the root

Post-order

l.subtree, r.subtree, node

BST Definition

1. l. subtree contains values < root
2. r. subtree contains values >= to the root
3. l. & r. subtree are BST

insert: log(n) search: log(n)

Example of DFS using a adjacency list with itera

• Using a node implementation with iteration:

// This is easy to swap to a breadth-first approach by using a queue instead of a stack!
// Instead of popping from the top, we can shift from the front
function depthFirstIter(node) {
  let visited = new Set();
  let stack = [node];

  while (stack.length) {
    let node = stack.pop();

    // if this node has already been visited, then skip this node
    if (visited.has(node.val)) continue;

    // otherwise it hasn't yet been visited,
    // so print it's val and mark it as visited.
    console.log(node.val);
    visited.add(node.val);

    // then add its neighbors to the stack to be explored
    stack.push(...node.neighbors);
  }
}