binary tree implementation javascript
- Published
- Reading time
- 4 min read
- Length
- 625 words
On this page
Binary Tree Implementation in JavaScript#
Introduction#
Binary Tree is a data structure that represents a hierarchical structure with a root value and left and right subtrees. It is an important concept in Computer Science and used in various applications such as search algorithms, sorting algorithms, and data compression algorithms.
Implementation#
Here is a basic implementation of a Binary Tree in JavaScript:
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
return this;
}
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;
}
}
}
search(value) {
let currentNode = this.root;
while (currentNode) {
if (value === currentNode.value) {
return true;
}
if (value < currentNode.value) {
currentNode = currentNode.left;
} else {
currentNode = currentNode.right;
}
}
return false;
}
}
const tree = new BinaryTree();
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(1);
tree.insert(9);
console.log(tree.search(7)); // true
console.log(tree.search(8)); // falseFirst, we define a Node class that has a value, left, and right properties. The value property holds the value of the node, and the left and right properties hold the left and right children of the node, respectively.
Next, we define a BinaryTree class that has a root property that holds the root node of the tree. The insert method inserts a new node into the tree. If the tree is empty, it sets the new node as the root node. Otherwise, it traverses the tree to find the appropriate place to insert the new node.
The search method searches for a value in the tree. It starts at the root node and traverses the tree until it finds a node with the same value as the searched value, or until it reaches a leaf node without finding the value. If it finds the value, it returns true; otherwise, it returns false.
We can create an instance of the BinaryTree class and use the insert method to insert nodes into the tree. We can also use the search method to search for values in the tree.
Alternative Implementations#
There are many ways to implement a Binary Tree in JavaScript. Here are two alternative implementations:
Using Object Literal
const tree = {
value: 5,
left: {
value: 3,
left: {
value: 1,
left: null,
right: null
},
right: null
},
right: {
value: 7,
left: null,
right: {
value: 9,
left: null,
right: null
}
}
};
function search(tree, value) {
if (!tree) {
return false;
}
if (tree.value === value) {
return true;
}
if (value < tree.value) {
return search(tree.left, value);
} else {
return search(tree.right, value);
}
}
console.log(search(tree, 7)); // true
console.log(search(tree, 8)); // falseThis implementation uses an object literal to represent the tree. The value, left, and right properties of each node are nested objects within the tree object. The search function is a recursive function that traverses the tree to find the searched value.
Using Functional Programming
const tree = {
value: 5,
left: {
value: 3,
left: {
value: 1,
left: null,
right: null
},
right: null
},
right: {
value: 7,
left: null,
right: {
value: 9,
left: null,
right: null
}
}
};
function search(tree, value) {
if (!tree) {
return false;
}
if (tree.value === value) {
return true;
}
return search(tree.left, value) || search(tree.right, value);
}
console.log(search(tree, 7)); // true
console.log(search(tree, 8)); // falseThis implementation uses functional programming to implement the tree. The tree is represented as nested function calls that return objects with a value property and two functions, left and right, that return the left and right subtrees, respectively. The search function is a recursive function that traverses the tree to find the searched value.