Binary tree in javascript

Introduction

A binary tree is a data structure where each element(node) can have maximum two children.

In this article- i am going to tell you how we can implement binary tree in javascript . So let’s code

Code

class Node {
    constructor(data) {
        this.data = data;
    }
}
class BinaryTree {
    constructor() {
        this.root = new Node(2);
        this.root.left = new Node(7);
        this.root.right = new Node(5);
    }
}

The program is simple - A binary tree contains a root element which is a node & it contains another two node which is at left position & right position. Like root element, every node contains another two node at left position & right position. A node has three part - data, left & right.

One of the type of binary tree is binary search tree which contains data in sorted order. For more information about binary search tree, read this article.

Traversal

Now let’s see how to traverse the tree. There are three types of traversal -

• Inorder traversal- first visit left node then root and in last right node.
• Preorder traversal- first visit root node then left and in last right node.
• Postorder traversal- first visit left node then right and in last root node.

Let’ write the program to traverse data-

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class BinaryTree {
    constructor() {
        this.root = new Node(2);
        this.root.left = new Node(10);
        this.root.right = new Node(5);
   }
    inOrderTraverse() {
        const traverse = (node) => {
            if (node != null) {
                traverse(node.left);
                console.log(node.data);
                traverse(node.right);
            }
        }
        traverse(this.root);
    }
   preOrderTraverse() {
        const traverse = (node) => {
            if (node != null) {
                console.log(node.data);
                traverse(node.left);
                traverse(node.right);
            }
         }
        traverse(this.root);
    }
    postOrderTraverse() {
        const traverse = (node) => {
            if (node != null) {
                traverse(node.left);
                traverse(node.right);
                console.log(node.data);
            }
         }
        traverse(this.root);
    }
}
const tree = new BinaryTree();
tree.inOrderTraverse();
tree.preOrderTraverse();
tree.postOrderTraverse();

Searching

Searching in binary tree can be done by two ways -

• BFS - search the element breadth wise i.e check left element first & then right element
• DFS - searching depth wise i.e check all left side first and then right side or right side first and then left side.

Let’s see every one of them -

BFS

The BFS algorithm check element row wise that is check all left & right element of a row first before proceeding to next row.

Let’s see the program to make it more clear -

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
class BinaryTree {
  constructor() {
    this.root = new Node(2);
    const leftNode = new Node(10);
    leftNode.left = new Node(22);
    leftNode.right = new Node(123);
    this.root.left = leftNode;
    this.root.right = new Node(5);
  }
  bfs(searchValue) {
    const search = (tree) => {
      var queue = []
      queue.push(tree);
      while (queue.length !== 0) {
        for (let i = 0; i < queue.length; i++) {
          var node = queue.shift()
          if (node.data === searchValue) {
            return node
          }
          // search breadth wise, so push left & right node
          if (node.left) {
            queue.push(node.left)
          }
          if (node.right) {
            queue.push(node.right)
          }
        }
      }
      return null
    }
    return search(this.root);
   }
}
const tree = new BinaryTree();
tree.bfs(22);

DFS

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class BinaryTree {
    constructor() {
        this.root = new Node(2);
        const leftNode = new Node(10);
        leftNode.left = new Node(22);
        leftNode.right = new Node(123);
        this.root.left = leftNode;
        this.root.right = new Node(5);
    }
    dfs(searchValue) {
        var stack = []
        stack.push(this.root);
        while (stack.length !== 0) {
            for (let i = 0; i < stack.length; i++) {
                var node = stack.pop()
                if (node.data === searchValue) {
                    return node
                }
                // search breadth wise, so push left & right node
                if (node.left) {
                    stack.push(node.left)
                }
                if (node.right) {
                    stack.push(node.right)
                }
            }
        }
        return null
    }
}
const tree = new BinaryTree();
tree.dfs(22);

As you can see the only difference between bsf & dfs is that bfs uses queue but dfs uses stack & of course due to this they are searching for element in different way.

Thanks for reading it guys. Hope you find it useful.