TREES

Trees

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.

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.

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;
}