Internship at OpenGenus

Get this book -> Problems on Array: For Interviews and Competitive Programming

Binary Trees are sorts of data structures that have numerous employments. They can be applied in search, 3D computer games, high-bandwidth network switches, some shared projects and cryptography. In this article, we'll investigate the fundamentals and use of double trees and how to implement Binary Tree in JavaScript. We will likewise execute a paired tree model.

Following sections in this article:

  1. What is a Binary Tree
  2. Types of Binary Treess
  3. Basic Structures
  4. Operations of a Binary Tree
  5. How do we build one

What is a Binary Tree

A binary tree is only an ordinary tree with the impediment of every node merely having the option to, probably, have two children. A binary tree simply has the extra principle that on the off chance that there are two qualities, at that point they should be arranged.

Here's a visualized example:
10
/
8 12
/ \ /
4 9 11 15

Types of Binary Trees
There are three unique kinds of parallel trees that will be talked about in this article:

  1. Full binary tree: Every node other than leaf nodes has 2 child nodes.
  2. Complete binary tree: All levels are filled aside from potentially the last one, and all nodes are filled in as extreme left as could be expected under the circumstances.
  3. Perfect binary tree: All nodes have two children and all leaves are at a similar level.

Basic Structure of a Binary Tree
In a Binary tree there are three things one should know:

  1. Root: This is the top node of a tree structure and it doesn't have a parent.
  2. Parent: It's an archetype node.
  3. Child: It's the replacement of a parent node.

Basic Operations on a Binary Tree

  1. Create: creates an empty tree.
  2. Insert: insert a node in the tree.
  3. Search: Searches for a node in the tree.
  4. Delete: deletes a node from the tree.

How do we bulid one?
I'm happy you inquired! How about we experience the means together to assemble one out in modern JavaScript.
We will construct our BST utilizing ES6 Class language structure, and it should in reality all be possible inside one class!
We should declare it first, and work out our constructor simultaneously:

            class Node {   constructor(data) {    this.data = data;    this.left = null;    this.right = null;   } }

How can we implement a Binary Tree?
One of the ways we can implement a binary tree and one that is most commonly used is -
1. * Dymanically created nodes; dymanically created nodes are linked to each other using pointers in the most common way. Nodes dymanically created at random locations in memory lined together through pointers.
In special cases we can implement Binary Trees by using Arrays. Arrays are typically used for complete Binary Tree.

Now let's implement a binary tree with JavaScript
If we make a binary search tree class and the node class, it will look as followed essence. Node has worth, left and right ascribes and binary tree has root quality.

                          const LEFT = 0;     const RIGHT = 1;      class TreeNode {       constructor(value) {         this.value = value;         this.descendents = [];         this.parent = null;       }        get left() {         return this.descendents[LEFT];       }        set left(node) {         this.descendents[LEFT] = node;         if (node) {           node.parent = this;         }       }        get right() {         return this.descendents[RIGHT];       }        set right(node) {         this.descendents[RIGHT] = node;         if (node) {           node.parent = this;         }       }     }

Alright, up until now, we can add a left and right child. Now, how about we do the BST class that upholds the left < parent < right rule.

                          class BinarySearchTree {       constructor() {         this.root = null;         this.size = 0;       }       add(value) { /* ... */ }       find(value) { /* ... */ }       remove(value) { /* ... */ }       getMax() { /* ... */ }       getMin() { /* ... */ }     }

Let's implementing Insertion.

To insert a node in a binary tree, we do the accompanying:

  1. On the off chance that a tree is vacant, the first node turns into the root, and you are finished.
  2. Analyze root/parent's value if it's higher go right, if it's lower go left. In the event that it's the equivalent, at that point the value as of now exists so you can expand the copy tally (assortment).
  3. Repeat #2 until we found a vacant space to insert the new node.

We should do a delineation how to embed 30, 40, 10, 15, 12, 50:

                          add(value) {         const newNode = new BinaryTreeNode(value);         if (this.root) {           const { found, parent } = this.findNodeAndParent(value); // <1>           if (found) { // duplicated: value already exist on the tree             found.meta.multiplicity = (found.meta.multiplicity || 1) + 1; // <2>           } else if (value < parent.value) {             parent.setLeftAndUpdateParent(newNode);           } else {             parent.setRightAndUpdateParent(newNode);           }         } else {           this.root = newNode;         }          this.size += 1;         return newNode;       }       // end::add[]

Deletion

Have you ever attempted how might we erase a node from a binart tree? Deletion has consistently been an interesting idea in data structures. On account of binary trees, deletion is somewhat confounded yet once you read through this article I wager that you won't ever fail to remember how to delete a node from a binart tree. Thus, we should start:

Most importantly, we should know the property of a Binary Tree that values in the left subtree are not exactly the incentive at root and values in the right subtree are more prominent than the value at the root.

                          remove(value) {       const nodeToRemove = this.find(value);       if (!nodeToRemove) return false;        // Combine left and right children into one subtree without nodeToRemove       const nodeToRemoveChildren = this.combineLeftIntoRightSubtree(nodeToRemove);        if (nodeToRemove.meta.multiplicity && nodeToRemove.meta.multiplicity > 1) {         nodeToRemove.meta.multiplicity -= 1; // handle duplicated       } else if (nodeToRemove === this.root) {         // Replace (root) node to delete with the combined subtree.         this.root = nodeToRemoveChildren;         this.root.parent = null; // clearing up old parent       } else {         const side = nodeToRemove.isParentLeftChild ? 'left' : 'right';         const { parent } = nodeToRemove; // get parent         // Replace node to delete with the combined subtree.         parent[side] = nodeToRemoveChildren;       }        this.size -= 1;       return true;     }

Different types of traversal
Traversal is a process to visit all the nodes of a tree and may print their values as well. Since all nodes are associated through edges (links) we generally start from the root (head) node. That is, we can't arbitrarily get to a node in a tree. There are three different ways which we use to traverse a tree −
1. In-order Traversal
1. Pre-order Traversal
1. Post-order Traversal
Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it contains.

Summary
We have covered much ground binary tree. Let's sum it up with bullets:

  • The tree is a data structure where a node has 0 or more children.
  • Trees with two children or less are called: Binary Tree
  • When a Binary Tree is sorted so that the left value is less than the parent and the right children is higher, then and only then we have a Binary Search Tree.