Binary Tree — BFS, DFS — JavaScript

This article is to learn how to do Breadth-First Search(BFS), Depth-First Search(DFS) in a binary tree using JavaScript. If you want to learn Basic data structure using JavaScript, check here.

Binary Tree

The binary tree is a tree data structure in which each node has two children, which are referred to as the left child and the right child.

There are two search techniques in a binary tree,

  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)

Breadth-First Search (BFS)

In BFS, all nodes in each level (horizontally) should be visited before to go next level.

Algorithm

  1. Initialize
  • queue with root node
  • bfsValues — [] — to hold result values
  • tempNode

2. do below while queue length > 0

  • pop queue and load into tempNode
  • Add tempNode value into bfsValues
  • check tempNode left node, if node exists, add to queue
  • check tempNode right node, if node exists, add to queue

Depth-First Search (DFS)

In DFS, all nodes in each level (vertically) should be visited before to go next level.

Algorithm

  1. Initialize
  • stack with root node
  • dfsValues — [] — to hold result values
  • tempNode

2. do below while stack length > 0

  • shift stack and load into tempNode
  • Add tempNode value into dfsValues
  • check tempNode right node, if node exists, add to the stack
  • check tempNode left node, if node exists, add to the stack

Software engineer who passionate about learning technology. I strongly believe that Technologies are not just to learn, Technologies are to make our life easier