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.
Implementations
- 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
}
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);
}
}
}
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];
}
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
Three scenarios in finding the child to replace deleted node:
1.Removed node has no right child - The left child replaces the removed node
2.Removed node has a right child that has no left child - right child replaces the removed node
3.Removed node has a right child which has a left child - the right child's left most child replaces the removed node
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;
}
(iv). Tree Traversal
Here we enumerate nodes in a well defined order.
Basic Algorithm;
Process Node
Visit left
Visit right
There are three common orders. They vary in the steps.
- Preorder traversal
Process Node
Visit left
Visit right
- Postorder traversal
Visit left
Visit right
Process Node
- Inorder traversal
Visit left
Process Node
Visit right
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);
}
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
Note:Different helper methods can be declared as per requirements.
Top comments (0)