Hello everyone! 👋🏻 Hope you all are good ✨

Today, we are going to learn another useful data structure i.e Trees 🚀

Trees

A tree is a data structure where a node can have zero or more children nodes. Each node contains a value, and similar to graphs each node can have a connection between other nodes called an edge. A tree is a type of graph but not all graphs are trees.

Following are some terminologies of trees:

• The topmost node, also known as the parent node is called a Root Node.
• A node without any child is called Leaf Node .
• Nodes having the same parent node are called Sibling Nodes .
• The total distance between the last leaf node and the root node is called Height Of Tree
• Each hierarchy of children is called Level .

Applications Of Trees

Trees have so many applications but some of the most popular ones are:

• Trees are widely used to store hierarchical data, like folder structures, organization structures, XML/HTML, JSON data.

• Have you ever worked with DOM? 🤭 One of the most intuitive examples of a tree data structure in the world of programming is the Document Object Model (DOM) in HTML.

• Trees are widely used in applications where searching is the primary task. Since tree stores data in proper hierarchical order, therefore searching can be performed very quickly.

• Trees are widely used in machine learning and data modeling. We have decision trees for taking decisions based on particular criteria.

Types Of Trees

There are tons of types of trees in the world of computer science. You can visit this Wikipedia page if you are interested to explore all of them.

Here are some of the famous ones you'll come across:

1. General Tree
2. Binary Tree
3. Binary Search Tree
4. AVL Tree

🌳 General Tree

In General Tree, one node can have any amount of nodes and subtrees. This is called a Super Set of all the trees because it doesn't have any constraints.

🌳 Binary Tree

The most popular tree type ever. The binary tree is the kind of tree in which a node can have at most two children nodes. These two children nodes are called the left child and right child.

🌳 Binary Search Tree

A Binary Search Tree is a form of a binary tree with the following restrictions.

• The left child value of a node should in BST be less than or equal to the parent value.
• The right child value should always be greater than or equal to the parent’s value.
• The left and right subtrees must also be a binary search tree.

These restrictions help us to perform efficient searches because it makes it easy to determine where the node is based on the node value in the subtree.

This is the reason why we call it Binary Search Tree 😄

🌳 AVL Tree

An AVL tree is a type of binary search tree. AVL stands for Adelson, Velskii, and Landis, the creators of the AVL tree. AVL tree has a special feature which is called dynamic self-balancing. It adds one more restriction on top of the binary search tree that is:

The difference between the depth of right and left sub-trees cannot be more than one. This difference is called the balance factor.

The implementation of the AVL tree should include the balancing feature whenever the node is inserted or removed to maintain the balance factor which guarantees the AVL tree.

To understand the AVL in detail, please watch: AVL Tree - Insertion and Rotations

Implementing Tree In JavaScript

In this article, we are going to implement the general tree using JavaScript.

We will implement the following functions in our tree:

• addChild: To add a child of a node.
• removeChild: To remove a child of a node.
• getChilds: Get all the children of a node.
• getChild: Get single child (Search).
• setParent: Set parent of a node.
• getParent: Get the parent of a node.

👉 TreeNode class

Let's create a node class and name it TreeNode. It will have a constructor in which we will receive the value of the node.

The node will have three properties/attributes:

1. value: The value of the node. Could be anything.
2. children: All the children of the node. Could be one or N
3. parent: The parent of the node. Always be one.

class TreeNode {
  constructor(value) {
    // Value of the Node
    this.value = value;
    // Node can have one or more childrens,
    // therefore we are using an array to hold child nodes
    this.children = [];
    // A node can have only one element as parent.
    this.parent = null;
  }
}

👉 Adding A Child

We will create a method addChild which will accept an argument of the TreeNode object. We will add this node to the children array.

addChild(childNode) {
  // push the children into the children array.
  // Improvement: We can make it unique.
  this.children.push(childNode);
  return this.children;
}

👉 Remove A Child

We will create a method removeChild which will accept an argument of the TreeNode object. We will delete this node and will update the children's array.

I'm using filter of javascript, you can implement your efficient algorithm to achieve delete.

removeChild(childNode) {
  this.children = this.children.filter((node) => {
    return node.value !== childNode.value;
  });
}

👉 Get All The Childs

Nothing to explain here 😂

getChilds() {
  return this.children;
}

👉 Get Single Child

We will pass the childNode for search criteria and search in the children array. If the node is found, we will return it, otherwise, we will return the message "Child not found".

getChild(childNode) {
  const node = this.children.find((node) => node.value === childNode.value);
  return node || "Child not found";
}

👉 Setting The Parent

We have a property called parent on TreeNode that holds the record of the parent node of a node. We will create a method setParent that will accept a node of TreeNode and we will set the parent of the current node to this node.

setParent(node) {
  this.parent = node;
  return this.parent;
}

👉 Get The Parent

Nothing to explain here as well 😂

getParent() {
  return this.parent;
}

Let's Create A Tree 🌲

/**
 * let's implement this tree now:
 *
 *        1
 *    2       3
 * 4    5         6
 */

const firstNode = new TreeNode(1);
const secondNode = new TreeNode(2);
const thirdNode = new TreeNode(3);
const fourthNode = new TreeNode(4);
const fifthNode = new TreeNode(5);
const sixthNode = new TreeNode(6);

// Let's create tree structure by adding childs and parents
firstNode.addChild(secondNode);
secondNode.setParent(firstNode);

firstNode.addChild(thirdNode);
thirdNode.setParent(firstNode);

// for second node
secondNode.addChild(fourthNode);
fourthNode.setParent(secondNode);
secondNode.addChild(fifthNode);
fifthNode.setParent(secondNode);

// for third node
thirdNode.addChild(sixthNode);
sixthNode.setParent(thirdNode);

console.log('Tree: ', firstNode);

thirdNode.removeChild(sixthNode);

console.log('After removal: ', firstNode);

console.log('Childs of first node:', firstNode.getChilds());

console.log('Second Child of first node', firstNode.getChild(secondNode));

Complete example 👇

---

That's it, folks! hope it was a good read for you. Thank you! ✨

👉 Follow me: Github Twitter LinkedIn Youtube