Tree Traversing In JavaScript

Posted By : Rajan Rawat | 23-Jun-2017

Trees which are used in data structures in Web development. This applies to developers and users. Who wrote HTML for each web development being loaded into a web browser to create a tree, which is called the DOM (Document Object Model). Everyone on the Internet, which in turn uses information on the internet, leads to the tree: DOM.

Now, here is the twist.This article that you are reading right now is rendered in your browser as a tree and paragraph that you are reading is right now represented as text in a <p> element; the <p> element is nested inside a <body> element; and the <body> element is nested inside an <html> element.

In this blog we have to create a tree using two different methods first is depth first search(DFS) and second is breadth first search. Both of these have thier different ways of interacting with a tree, both will travel and incorporate use of data-structures. DFS will use a stack and BFS will use a queue to visit nodes.

Depth First Search and Breadth-First Search

We are using node and pointers to describe the tree

operations of a tree

So every tree have the nodes, which can be separate constructor from a tre, so we have to outline the operations of both constructor node and trees

Implementation of a Tree

now we have to write a code for a tree

Properties of a node

now for the implementation of a tree we will define a fucntion call node and constructor call tree.

     function Node(data){
	this.data = data;
	this.parent = null;
	this.children = [];
}

now each and every instacne of node will contain things data, parent and children

Properties of a Tree

 function Tree(data){
 var node = new Node(data);
 this._root = node;
 }

Methods of a tree

we will create some methods for tree

traverseDF(callback)
traverseBF(callback)
contains(data,traversal)
add(child,parent)
remove(node,parent)

Complete implementation of tree

DFS

             Tree.prototype.traverse = function (callback) {
  var stack=[this];
  var n;

  while(stack.length>0) {

    n = stack.pop();
    callback(n.value);

    if (!n.children) {
      continue;
    }

    for (var i = n.children.length-1; i>=0; i--) {
       stack.push(n.children[i]);
    }
  }
};

BFS

       Tree.prototype.traverse = function (callback) {
  var queue=[this];
  var n;

  while(queue.length>0) {

    n = queue.shift();
    callback(n.value);

    if (!n.children) {
      continue;
    }

    for (var i = 0; i< n.children.length; i++) {
       queue.push(n.children[i]);
    }
  }
};