In JavaScript, a tree is a hierarchical data structure consisting of nodes connected by edges. Each node in a tree contains a value and a list of references (or pointers) to its child nodes. Trees are used to represent hierarchical relationships between data, such as organizational structures, file systems, and hierarchical data in databases.
Terminology:
- Node: Each element in a tree is called a node. A node contains a value and references to its child nodes.
- Root: The topmost node in a tree. It has no parent node.
- Parent: A node that has child nodes.
- Child: A node directly connected to another node when moving away from the root.
- Leaf: A node with no children.
- Depth: The level of a node in a tree. The root node is at depth 0, its children are at depth 1, and so on.
- Height: The height of a tree is the maximum depth of any node in the tree.
- Subtree: A tree rooted at a node, which includes all of its descendants.
Types of Trees:
Binary Tree: A binary tree is a tree in which each node has at most two children, referred to as the left child and the right child.
Binary Search Tree (BST): A binary search tree is a binary tree in which the values of nodes in the left subtree are less than the value of the root node, and the values of nodes in the right subtree are greater than the value of the root node.
Balanced Tree: A balanced tree is a tree in which the heights of the two subtrees of any node never differ by more than one. Examples include AVL trees, Red-Black trees, and B-trees.
N-ary Tree: An N-ary tree is a tree in which each node can have at most N children.
Operations:
- Traversal: Traversing a tree allows you to visit each node in a specific order. Common tree traversal algorithms include in-order, pre-order, post-order, and level-order traversal.
Search: Searching for a value in a tree involves traversing the tree and comparing the value of each node until the target value is found or the entire tree is searched.
Insertion: Inserting a new node into a tree involves finding the appropriate location in the tree based on the value of the node and adding it as a child of an existing node.
Deletion: Deleting a node from a tree involves removing the node from the tree while maintaining the tree’s properties.
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode =
new TreeNode(value);
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode
(this.root, newNode);
}
}
insertNode(node, newNode) {
if (newNode.value < node.value) {
if (node.left === null) {
node.left = newNode;
} else {
this.insertNode
(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
this.insertNode
(node.right, newNode);
}
}
}
search(value) {
return this.searchNode
(this.root, value);
}
searchNode(node, value) {
if (node === null) {
return false;
}
if (value === node.value) {
return true;
}
if (value < node.value) {
return this.searchNode
(node.left, value);
} else {
return this.searchNode
(node.right, value);
}
}
}
// Example usage:
let bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
console.log(bst.search(5));
// Output: true
console.log(bst.search(20));
// Output: false
