DEV Community

Ivy-Walobwa
Ivy-Walobwa

Posted on

Binary Trees

#javascript #webdev

A binary tree is a sorted hierarchy of data.

It consists of;
1.A root node
2.0-2 children

The structure is such that the smallest values are on the left child node while the largest values on the right child node.

binary tree

Implementations

  1. Create the node class and binary tree class 
class Node{ constructor(data) { this.data = data; this.left = null; this.right = null; } } class BinaryTree{ constructor() { this.root = null; } //add methods }
Enter fullscreen mode Exit fullscreen mode

Our node contains the data, left and right child. Our binary tree has a root node which is set to null.

2.Add methods to class

(i).Adding Data
We add data to the binary tree using a recursive algorithm.
case 1 -> empty tree: new node becomes the root node
case 2 -> smaller value: recursively added to the left
case 3 -> larger value: recursively added to the right
equal value -> treat as a larger value

add(data) { const newNode = new Node(data); if (this.root === null) { this.root = newNode; } else { this._addTo(this.root, newNode); } } _addTo(currentNode, newNode) { if (newNode.data < currentNode.data) { if (currentNode.left === null) { //if new node is less than the current node //add to left currentNode.left = newNode; } else { this._addTo(currentNode.left, newNode); } } else { //if new node is greater than/ equal to the current node //add to right if (currentNode.right === null) { currentNode.right = newNode; } else { this._addTo(currentNode.right, newNode); } } }
Enter fullscreen mode Exit fullscreen mode

I put an underscore before the addTo method to hint me that it is meant to act as a private method.

(ii).Searching

 //try find data in tree contains(data) { let current = this.root; let parent = null //while we don't have a match while (current !== null) { if (data < current.data) { //if value is less than current, go left parent = current; current = current.left; } else if (data > current.data) { //if value is greater than current, go right parent = current; current = current.right; } else { //we have a match break; } } return[ current, parent ]; } find(data) { //return first value returned by contains() method return this.contains(data)[0]; }
Enter fullscreen mode Exit fullscreen mode

While implementing the remove operation, I realized I needed to check if the node to be removed exists and return the node and its parent. Adding the contains method saved me from duplicating code.
The contains method checks if a node exists and if it does, returns an array containing the found node and its parent.
The find method returns the first value of the array which is the node we are looking for.

(iii)Remove
This was honestly a tough one for me. Took me more than 8hrs to understand how it works.

A simple walk through before we jump into code 😉 .

find node to be deleted if node does not exists, exit if node is terminal node remove parent's pointer to the deleted node if node is not terminal node find the child to replace the deleted node
Enter fullscreen mode Exit fullscreen mode

Three scenarios in finding the child to replace deleted node:

1.Removed node has no right child - The left child replaces the removed node

binary tree

2.Removed node has a right child that has no left child - right child replaces the removed node

binary tree

3.Removed node has a right child which has a left child - the right child's left most child replaces the removed node

binary code

The code

 remove(data) { let parent = this.contains(data)[1]; let current = this.find(data); if (current === null) { return false; } //CASE 1 //removing node with no right child //its left child replaces the removed node if (current.right === null) { if (parent === null) { //if we are removing root node this.root = current.left; } else { if (parent.data > current.data) { //make current left child, left child of parent //rare case parent.left = current.left; } else if (parent.data < current.data) { //make current left child, right child of parent parent.right = current.left; } } } //CASE 2 //removing node whose right child has no left child //right child replaces the removed node else if (current.right.left === null) { //move removed node left child to the left of removed's right current.right.left = current.left; if (parent === null) { this.root = current.right; } else { if (parent.data > current.data) { //make current right child a left child of parent parent.left = current.right; } else if (parent.data < current.data) { //make current right child a right child of parent parent.right = current.right; } } } //CASE 3 //if removed node's right child has a left child //replace removed with its right child's left most node else { //find right leftmost child let leftMost = current.right.left; let leftMostParent = current.right; while (leftMost.left != null) { //move to the left most node of the right child leftMostParent = leftMost; leftMost = leftMost.left; } //the parent's left subtree becomes the leftmost's right subtree leftMostParent.left = leftMost.right; //assign leftmost's left n right to current's left n right leftMost.left = current.left; leftMost.right = current.right; if (parent === null) { this.root = leftMost; } else { if (parent.data > current.data) { //make leftmost the parent's left child parent.left = leftMost; } else if (parent.data < current.data) { //make leftmost the parent's right child parent.right = leftMost } } } return true; }
Enter fullscreen mode Exit fullscreen mode

(iv). Tree Traversal
Here we enumerate nodes in a well defined order.

Basic Algorithm;

Process Node Visit left Visit right
Enter fullscreen mode Exit fullscreen mode

There are three common orders. They vary in the steps.

  • Preorder traversal 
Process Node Visit left Visit right
Enter fullscreen mode Exit fullscreen mode
  • Postorder traversal 
Visit left Visit right Process Node
Enter fullscreen mode Exit fullscreen mode
  • Inorder traversal 
Visit left Process Node Visit right
Enter fullscreen mode Exit fullscreen mode

The code

 //TREE TRAVERSAL preorder(current) { if (current === null) { return; } console.log(current.data); this.preorder(current.left); this.preorder(current.right); } postorder(current) { if (current === null) { return; } this.postorder(current.left); this.postorder(current.right); console.log(current.data); } inorder(current) { if (current === null) { return; } this.inorder(current.left); console.log(current.data); this.inorder(current.right); }
Enter fullscreen mode Exit fullscreen mode

Sample test code

const tree = new BinaryTree(); tree.add(4); tree.add(2); tree.add(1); tree.add(3); tree.add(6); tree.add(5); tree.add(7) tree.find(6); tree.remove(6) tree.postorder(tree.root) // 1 3 2 5 7 6 4 tree.preorder(tree.root) // 4 2 1 3 6 5 7 tree.inorder(tree.root) // 1 2 3 4 5 6 7
Enter fullscreen mode Exit fullscreen mode

Note:Different helper methods can be declared as per requirements.

Top comments (0)