Tree Traversal

1. Depth-First Traversals
2. Breadth-First Traversal
3. Resources

There are a few different ways to traverse trees. Each different type is used in different situations. Here are the common types of tree iterations

Depth-First Traversals (Preorder, Postorder and Inorder)

When to use

• Preorder
  • You want to encounter roots before visiting leaves
• Postorder
  • Use this when you want to visit both children before the parents
  • You don't waste any time inspecting roots in search for leaves
• Inorder
  • Gives the nodes from smallest to greatest, used to flatten the tree

BinaryTree.prototype.preorder = function(cb, node = this.head) {
  cb(node.value) // <--------------Preorder has cb at the beginning of the method

  if(node.left) {
    this.preorder(cb, node.left)
  }
  if(node.right) {
    this.preorder(cb, node.right)
  }
}

BinaryTree.prototype.postorder = function(cb, node = this.head) {
  if(node.left) {
    this.postorder(cb, node.left)
  }
  if(node.right) {
    this.postorder(cb, node.right)
  }

  cb(node.value) // <--------------Postorder has cb at the end of the method
}

BinaryTree.prototype.inorder = function(cb, node = this.head) {
  if(node.left) {
    this.inorder(cb, node.left)
  }

  cb(node.value) // <--------------Inorder has cb in the middle of the method


  if(node.right) {
    this.inorder(cb, node.right)
  }
}

Breadth-First Traversal (Level-Order Traversal)

• Breadth-first finds all nodes, one line at a time
• Use a queue instead of a stack to implement

BinaryTree.prototype.breadthFirst = function(cb) {
  let queue = [this.head]
  let n = null

  while(queue.length > 0) {
    n = queue.shift()
    cb(n)

    if(n.left) {
      queue.push(n.left)
    }
    if(n.right) {
      queue.push(n.right)
    }
  }
}

Resources

• JS: Binary Search Tree methods