Your Web News in One Place

Sources Contact Advanced Search Tutorials

An Interest In:

Web News this Week

Some of Our Sources

View All Sources

Help Webnuz

Referal links:

November 21, 2020 11:23 pm GMT

Trees In JavaScript

This week we are going to implement the trees data structure in JavaScript.

Introduction

Trees are wonderful data structures that can model real life hierarchical information, including organizational charts, genealogical trees, computer file systems, HTML elements on a web page (also known as the Document Object Model, or DOM), state diagrams, and more.

A tree is composed of tree nodes. A tree node is a very simple data structure that contains:

Data

A list of children, where each child is itself a tree node
We can add data to and remove data from a tree and traverse it in two different ways:
Depth-first, or
Breadth-first
In this lesson, were going to implement the tree node data structure as a class in JavaScript.

class TreeNode {  constructor(data) {    this.data = data;    this.children = [];  }};

Enter fullscreen mode Exit fullscreen mode

Adding a Child

The next task is to add a child to our tree. Each child in our children array has to be an instance of a TreeNode, however we want to allow our user interface to accept adding data in other forms as well.

For instance, if our method to add a child is .addChild(), we want to accommodate calling tree.addChild(3) as well as tree.addChild(new TreeNode(3)).

class TreeNode {  constructor(data) {    this.data = data;    this.children = [];  }  addChild(child) {    if (child instanceof TreeNode) {      this.children.push(child);    } else {      this.children.push(new TreeNode(child));    }  }};

Enter fullscreen mode Exit fullscreen mode

Removing a Child

Like with .addChild(), we want to provide a flexible interface for removing a child from a tree based on either its data or a TreeNode match. For example, if our method to remove a child is .removeChild(), we want to be able to execute the following:

const blue = 'blue';const green = new TreeNode('green');tree.addChild(blue);         // add datatree.addChild(green);        // add TreeNodetree.removeChild('blue');    // remove by datatree.removeChild(green);    // remove by TreeNode

Enter fullscreen mode Exit fullscreen mode

The generic steps to execute in removing a child from a tree are as follows:

If target child is an instance of TreeNode,  Compare target child with each child in the children array  Update the children array if target child is foundElse   Compare target child with each child's data in the children array  Update the children array if target child is foundIf target child is not found in the children array  Recursively call .removeChild() for each grandchild.

Enter fullscreen mode Exit fullscreen mode

Because we implemented the children as an array, we can use the array .filter() method to update children. Like with .addChild(), we can also use instanceof to check if our target child is an instance of a TreeNode.

class TreeNode {  constructor(data) {    this.data = data;    this.children = [];  }  addChild(child) {    if (child instanceof TreeNode) {      this.children.push(child);    } else {      this.children.push(new TreeNode(child));    }  }  removeChild(childToRemove) {    const length = this.children.length;    this.children = this.children.filter(child => {      if (childToRemove instanceof TreeNode) {        return childToRemove !== child;      } else {        return child.data !== childToRemove;      }    });    if (length === this.children.length) {      this.children.forEach(child => child.removeChild(childToRemove));    }  }};

Enter fullscreen mode Exit fullscreen mode

Pretty Print

Wouldnt it be nice to be able to display the structure of our tree in a captivating visual way? We have provided a helpful method, .print() that will give you a formatted text display of our tree.

For example, a tree with 3 levels starting with root node 15, children 3, 12, 0, and grandchildren 6, 9, 19, 8, 10, 19 is displayed below:

15-- 3-- -- 6-- -- 9-- 12-- -- 19-- -- 8-- 0-- -- 10-- -- 19

Enter fullscreen mode Exit fullscreen mode

This method takes one parameter, level, which is initialized to 0, to enable printing the entire tree structure from the top to the bottom

class TreeNode {  constructor(data) {    this.data = data;    this.children = [];  }  addChild(child) {    if (child instanceof TreeNode) {      this.children.push(child);    } else {      this.children.push(new TreeNode(child));    }  }  removeChild(childToRemove) {    const length = this.children.length;    this.children = this.children.filter(child => {      return childToRemove instanceof TreeNode      ? child !== childToRemove      : child.data !== childToRemove;    });    if (length === this.children.length) {      this.children.forEach(child => child.removeChild(childToRemove));    }  }  print(level = 0) {    let result = '';    for (let i = 0; i < level; i++) {      result += '-- ';    }    console.log(`${result}${this.data}`);    this.children.forEach(child => child.print(level + 1));  }};

Enter fullscreen mode Exit fullscreen mode

Depth-first Tree Traversal

Now that we can add nodes to our tree, the next step is to be able to traverse the tree and display its content. We can do this in one of two ways: depth-first or breadth-first.

Depth-first traversal visits the first child in the children array and that nodes children recursively before visiting its siblings and their children recursively. The algorithm is as follows:

For each node  Display its data  For each child in children, call itself recursively

Enter fullscreen mode Exit fullscreen mode

Based on this tree displayed using .print():

15-- 3-- -- 6-- -- 9-- 12-- -- 19-- -- 8-- 0-- -- 10-- -- 19

Enter fullscreen mode Exit fullscreen mode

we can traverse it depth-wise to produce this result:

153691219801019

Enter fullscreen mode Exit fullscreen mode

class TreeNode {  constructor(data) {    this.data = data;    this.children = [];  }  addChild(child) {    if (child instanceof TreeNode) {      this.children.push(child);    } else {      this.children.push(new TreeNode(child));    }  }  removeChild(childToRemove) {    const length = this.children.length;    this.children = this.children.filter(child => {      return childToRemove instanceof TreeNode      ? child !== childToRemove      : child.data !== childToRemove;    });    if (length === this.children.length) {      this.children.forEach(child => child.removeChild(childToRemove));    }  }  print(level = 0) {    let result = '';    for (let i = 0; i < level; i++) {      result += '-- ';    }    console.log(`${result}${this.data}`);    this.children.forEach(child => child.print(level + 1));  }};

Enter fullscreen mode Exit fullscreen mode

Breadth-first Tree Traversal

On the to the hand,Breadth-first traversal visits each child in the children array starting from the first child before visiting their children and further layers until the bottom level is visited. The algorithm is as follows:

Assign an array to contain the current root nodeWhile the array is not empty  Extract the first tree node from the array  Display tree node's data  Append tree node's children to the array

Enter fullscreen mode Exit fullscreen mode

Based on this tree displayed using .print():

15-- 3-- -- 6-- -- 9-- 12-- -- 19-- -- 8-- 0-- -- 10-- -- 19

Enter fullscreen mode Exit fullscreen mode

we can traverse it breadth-wise to produce this result:

153120691981019

Enter fullscreen mode Exit fullscreen mode

class TreeNode {  constructor(data) {    this.data = data;    this.children = [];  }  addChild(child) {    if (child instanceof TreeNode) {      this.children.push(child);    } else {      this.children.push(new TreeNode(child));    }  }  removeChild(childToRemove) {    const length = this.children.length;    this.children = this.children.filter(child => {      return childToRemove instanceof TreeNode      ? child !== childToRemove      : child.data !== childToRemove;    });    if (length === this.children.length) {      this.children.forEach(child => child.removeChild(childToRemove));    }  }  print(level = 0) {    let result = '';    for (let i = 0; i < level; i++) {      result += '-- ';    }    console.log(`${result}${this.data}`);    this.children.forEach(child => child.print(level + 1));  }  depthFirstTraversal() {    console.log(this.data);    this.children.forEach(child => child.depthFirstTraversal());  }  breadthFirstTraversal() {    let queue = [ this ];    while (queue.length > 0) {      const current = queue.shift();      console.log(current.data);      queue = queue.concat(current.children);    }  }};

Enter fullscreen mode Exit fullscreen mode

Original Link: https://dev.to/wdiep10/trees-in-javascript-2a2a

Share this article:

Share on Facebook

View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To