What Is This Plant?
This is my first blog post of 2023 and I'd like to say Happy New Year!
Binary Search Trees are one of the fundamental data structures in Computer Science. Understanding them will make it easier to implement algorithms. I am actively applying for Software Engineer positions and if you're like me, some technical interviews require candidates to complete a coding assessment on-site, via Hackerrank or some other online platform. Practicing binary search trees is an important step in strengthening your programming skills. Other concepts that are important to grasp are heaps, sorting, recursion, and iteration.
Below is a list of different variations of the binary tree, all of which share the same characteristics such as the following:
They have nodes. Nodes are endpoints that store data, typically numbers.
Nodes are connected through edges. Edges are lines that represent the links between nodes in a tree.
Edges may have numbers written next to them, referred to as weights. The weights represent a parameter of traversal between two nodes such as the distance or time to travel between two cities.
Nodes that are the immediate link of another node can be referred to as neighbors.
It is important to note that Mathematicians refer to them as a vertex. In Computer Science, however, they are called Nodes. You can skip directly to the implementation below.
1. Graphs
Graphs are a type of tree that has an endless connection or a cycle. i.e. all the nodes are interlinked. The visual representation of a graph is traversed horizontally or using what is known as Breadth First Search, more on that later.
An illustration of a graph data structure:
2. Trees
Trees are a type of data structure that has a node at the top called the root. All traversals in a tree start at this root. In a tree, the preceding node is called a parent, and a subsequent node is called a child. Root nodes do not have a parent but can have children. Some Engineers say that 'every tree is a graph, but not every graph is a tree'.
An illustration of a tree data structure:
3. Binary Trees
In contrast to a regular tree, the nodes of a binary tree have a maximum of two children. Therefore, every binary tree is a tree but every tree is not necessarily a binary tree. Other important facts about trees are:
Any node that has 0 children is called a leaf node, this is usually the node on the last level of the tree.
Nodes that stem from one parent and are at the same level are called siblings.
4. Binary Search Trees
Binary Search Trees have the condition that every left child has a value that is less than the parent and every right child is greater than the parent. This condition makes it so that all the other descendants on either side follow the same order. If the tree does not meet this condition, then it does not qualify as a binary search tree but rather, it is classified as any of the other two trees.
A diagram that represents a binary search tree:
5. Types Of Binary Trees
All binary trees have different levels that start at 1 for the top level and continue to increase as we traverse the tree downwards vertically.
Complete: A binary tree is said to be complete if every level of the tree is full except the last level and every node on the last level has to be filled from the left-most node to the right-most node.
Full: A full binary tree is one where every node has either 0 or 2 children.
Perfect: This tree meets the condition to be both full and complete as defined above.
A diagram that represents a binary tree:
Depth First Search
Depth First Search, also known as DFS is a method of traversing a tree from the top to the bottom. The level defines the depth that the node sits as shown in the diagram above. In DFS, we start at the root, then the left sub-tree, then finally the right sub-tree.
Breadth-First Search
In contrast to DFS, Breadth First Search is a search technique that traverses the tree horizontally, starting from the left sub-tree to the right sub-tree.
Implementation
To start off, we can create a node class that instantiates an object with data, left, and right default properties.
A JavaScript class named Node:
class Node{
constructor(data, left = null, right = null){
this.data = data;
this.left = left;
this.right = right;
}
}
Next, we need to define another class that instantiates the binary tree itself and makes use of the Node class above to define its properties. The tree will have a default null value which will be returned this way unless another root is specified. The add() method is what will be used to insert nodes into the binary search tree.
A JavaScript class named BinarySearchTree:
class BinarySearchTree{
constructor(){
this.root = null;
}
add(data){
const node = this.root;
if(node === null){
this.root = new Node(data);
return;
} else {
const searchTree = function(node){
if(data < node.data){
if(node.left === null){
node.left = new Node(data);
return;
} else if(node.left !== null){
return searchTree(node.left);
}
} else if(data > node.data){
if(node.right === null){
node.right = new Node(data);
return;
} else if(node.right !== null){
return searchTree(node.right);
}
} else {
return null;
}
};
return searchTree(node);
}
}
findMin(){
let current = this.root;
while(current.left !== null){
current = current.left;
}
return current.data;
}
findMax(){
let current = this.root;
while(current.right !== null){
current = current.right;
}
return current.data;
}
find(data){
let current = this.root;
while(current.data !== data){
if(data < current.data){
current = current.left;
} else{
current = current.right;
}
if(current === null){
return null;
}
}
return current;
}
check(data){
let current = this.root;
while(current){
if(data === current.data){
return true;
}
if(data < current.data){
current = current.left;
} else {
current = current.right;
}
}
return false;
}
remove(data){
const removeNode = function(node, data){
if(node == null){
return null;
}
if(data == node.data){
// node has no children
if(node.left == null && node.right == null){
return null;
}
// node has no left child
if(node.left == null){
return node.right;
}
// node has no right child
if(node.right == null){
return node.left;
}
// node has no children
var tempNode = node.right;
while(tempNode.left != null){
tempNode = tempNode.left;
}
node.data = tempNode.data;
node.right = removeNode(node.right, tempNode.data);
return node;
} else if(data < node.data){
node.left = removeNode(node.left, data);
return node;
} else {
node.right = removeNode(node.right, data);
return node;
}
};
this.root = removeNode(this.root, data);
}
}
let tree = new BinarySearchTree(); // creating an instance of a binary search tree
tree.add(8);
tree.add(4);
tree.add(12);
tree.add(2);
tree.add(6);
tree.add(10);
tree.add(14);
The
findMin()method in theBinarySearchTreeclass will return the smallest value of the tree which is a leaf node on the left subtree.The
findMax()method in theBinarySearchTreeclass will return the largest value of the tree which is a leaf node on the right subtree.The
find()method in theBinarySearchTreeclass will return an object that contains data, left, and right properties of the specified node. For exampletree.find(12)will return Node {data: 12, left: Node, right: Node} which indicates that this node has both left and right children. A node with no left or right children will outputnullfor these properties respectively.The
check()method returns a boolean true or false depending on whether the argument passed is available in the tree or not.The
remove()method will delete a node from the tree only if the node has previously been inserted. You can calltree.check()to verify if the node is present.We can add nodes to the tree by calling the
tree.add()method. The argument to the add method will be stored as a value in the tree.
Bonus trick: Here is an equation to calculate how many nodes there are in a tree; 2 to the power of (depth + 1) - 1. In this equation, the depth is the total number of levels that are in the tree. I haven't yet figured out a way to implement this with code but I'm sure it will be a fun challenge.
I suggest you read some of my other written articles:
