Tree Data Structure

Tree data structure is the topic of my blog today. A tree is made up of nodes that hold some amount of data and a reference to all of its children. A child is located directly underneath any given node, which is its parent. Nodes on the same level (that are connected to the same parent node) are siblings. Data could be a string, an array, an object or a number. Iterating through all different elements of the tree in order to add or remove elements is a tree traversal. Two of the most common ways to traverse a tree are Breadth-First Traversal and Depth-First Traversal. Breadth-First Traversal is where we start at the root of the tree, the node on top, and move a level lower going from left to right, and repeat each level. Depth-First Traversal going all the way from the root of the tree to the left and go back up to the parent and repeat this top to bottom approach. For the first approach we are going to create a Tree Class and assign a root property to it, which points to the first node. In the construction we will initialize this.root property to be equal to null. A root node will go into a newly created array, we will iterate through this array using the while loop, while there are elements in this array, take out the first element, retrieve all of its children and put children back into the array. We will call every node in the tree with our inner function (fn) that gets passed to our traverseBF method as an argument. We call that function with the current element. We take the first element out of the array, retrieve its children and put it at the end of the array, we do it with every element in the array.

traverseDF(fn) {

const arr = [this.root];

while (arr.length) {

const node = arr.shift();

arr.unshift(…node.children);

fn(node);

}

}

Practicing algorithms will make it easy to solve them.

Happy Coding!