binary tree implementation javascript
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)); // false
First, 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)); // false
This 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)); // false
This 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.