Trees - Binary Trees, Binary Search Trees, Implementation, Binary Heaps & more
What is a tree?
A tree is a data structure in which a node can have zero or more children. Each node contains a value.
The reason this data structure is called a tree is simply because it resembles a tree. We start with a root node and branch off which each child of the root node. If a node has no children this is called a leaf node or terminal node.
What is a binary tree?
A binary tree is a tree in which each node has a maximum of two child nodes. A binary tree can have 0, 1 or 2 children on each node.
What is a binary search tree?
A binary search tree is a particular type of binary tree. Again, each node can have a maximum of two children, however, there is one particular rule they must follow:
The value of the left child of a parent node must be less than the value of the parent node & the value of the right child of a parent node must be greater than the value of the parent node. (see below)
Balanced vs Unbalanced Binary Search Trees
Binary Search trees can easily become unbalanced if they are not managed correctly.
e.g. imagine the root node has a value of 1 and therefore each time we insert a node, it will just form on the right hand side of the root node. (see below)
This isn't good......why? Well if we have an unbalanced BST then we lose efficiency. The more unbalanced the tree becomes the more the time complexity of the lookup, insertion, deletion etc becomes O(n).
With a balanced binary search tree, we can search efficiently as the tree is ordered on each level by value (left is lower, right is higher). This means that as the data set grows exponentially as we go down the tree, we just search the tree for one particular node before moving onto the next step. This makes the time complexity of balanced binary search trees: O(log n).
How can we balance a binary search tree?
The scope of my learning isn't how to balance a binary search tree, but we have AVL trees and Red-Black trees which are self balancing binary trees. Please read more on these types of trees if you are interested.
How can we implement a binary search tree?
Please see the below snippet for an implementation of a binary search tree.
There are methods involved for insertion & lookup. The method for deletion is a little more complex and I've attached a separate snippet of how this looks.
class Node {
constructor(value) {
this.left = null;
this.right = null;
this.value = value;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
} else {
let currentNode = this.root;
while (true) {
if (value < currentNode.value) {
if (!currentNode.left) {
currentNode.left = newNode;
return this;
}
currentNode = currentNode.left;
} else {
if (!currentNode.right) {
currentNode.right = newNode;
return this;
}
currentNode = currentNode.right;
}
}
}
}
lookup(value) {
if (!this.root) {
return false;
}
let currentNode = this.root;
while (currentNode) {
if (value < currentNode.value) {
currentNode = currentNode.left;
} else if (value > currentNode.value) {
currentNode = currentNode.right;
} else if (value === currentNode.value) {
return currentNode;
}
}
return false;
}
}
const tree = new BinarySearchTree();
tree.insert(9);
tree.insert(4);
tree.insert(6);
tree.insert(20);
tree.insert(170);
tree.insert(15);
tree.insert(1);
tree.lookup(10);
tree.lookup(6);
Deletion snippet:
remove(value)
if (!this.root) {
return false;
}
let currentNode = this.root;
let parentNode = null;
while(currentNode){
if(value < currentNode.value){
parentNode = currentNode;
currentNode = currentNode.left;
} else if(value > currentNode.value){
parentNode = currentNode;
currentNode = currentNode.right;
} else if (currentNode.value === value) {
//We have a match, get to work!
//Option 1: No right child:
if (currentNode.right === null) {
if (parentNode === null) {
this.root = currentNode.left;
} else {
//if parent > current value, make current left child a child of parent
if(currentNode.value < parentNode.value) {
parentNode.left = currentNode.left;
//if parent < current value, make left child a right child of parent
} else if(currentNode.value > parentNode.value) {
parentNode.right = currentNode.left;
}
}
//Option 2: Right child which doesnt have a left child
} else if (currentNode.right.left === null) {
currentNode.right.left = currentNode.left;
if(parentNode === null) {
this.root = currentNode.right;
} else {
//if parent > current, make right child of the left the parent
if(currentNode.value < parentNode.value) {
parentNode.left = currentNode.right;
//if parent < current, make right child a right child of the parent
} else if (currentNode.value > parentNode.value) {
parentNode.right = currentNode.right;
}
}
//Option 3: Right child that has a left child
} else {
//find the Right child's left most child
let leftmost = currentNode.right.left;
let leftmostParent = currentNode.right;
while(leftmost.left !== null) {
leftmostParent = leftmost;
leftmost = leftmost.left;
}
//Parent's left subtree is now leftmost's right subtree
leftmostParent.left = leftmost.right;
leftmost.left = currentNode.left;
leftmost.right = currentNode.right;
if(parentNode === null) {
this.root = leftmost;
} else {
if(currentNode.value < parentNode.value) {
parentNode.left = leftmost;
} else if(currentNode.value > parentNode.value) {
parentNode.right = leftmost;
}
}
}
return true;
}
}
}
}
What is a binary heap?
A binary heap is a tree which obeys the property that the root of any tree is greater than or equal to (or smaller than or equal to) all its children (heap property). The primary use of such a data structure is to implement a priority queue.
A priority queue is a special type of queue in which each element is associated with a priority value. It doesn't work on FIFO basis. Imagine a hospital ward, emergencies with higher priority will get attended to before non-urgent issues.
We can have a min heap or a max heap.