Binary Search Tree in JavaScript (Data Structures)

Short and Precise Js code to create a Binary Search Tree.

Photo by veeterzy on Unsplash

A binary Search Tree is a node-based binary tree data structure. It has the following properties:

1. Every parent node has at most two children.
2. Every node to the left is always less than the parent node.
3. Every node to the right is always greater than the parent node.

Tree Terminology:

1. Root: Topmost node in the tree.
2. Child: A node directly connected to another node when moving away from the root.
3. Parent: The converse notion of a child.
4. Siblings: A group of nodes with the same parent.
5. Leaf: A node with no children.
6. Edge: A connection between one node and another.

Todos:

1. Insert
2. Search

Creating a node: It contains a value and two pointers - left and right.

Binary Search Tree:

Insertion:

1. Create a node from the value passed in the function.
2. Starting at the root:

• Check if there is a root, if not, the new node becomes the root.
• If there is a root, check if the value of the new node is greater than or less than the value of the root.

3. If the value is greater: check to see if there is a node to the right.

• If there is, move to that node and repeat the steps.
• Add that node as the right property.

4. If the value is less: check to see if there is a node to the left.

• If there is, move to that node and repeat these steps.
• If there is not, add that node as the left property.

Search:

1. Starting at the root:

• Check if there is a root, if not then we’re done.
• If there is a root, check if the value of the new node is equal to the value we’re looking for. If found, we’re done.
• If not, check to see if the value is greater than or less than the value of the root.

2. If it’s greater: check to see if there is a node to the right.

• If there is a node, move to that node and repeat the same steps.
• If there’s not, we’re done searching.

3. If it’s less: check to see if there is a node to the left.

• If there is, move to that node and repeat the same steps.
• If there is not, we’re done searching.

Time Complexity of Binary Search Tree:

• Access: O(log(n))
• Search: O(log(n))
• Insertion: O(log(n))
• Removal: O(log(n))