Binary Search Tree: Inserting a Value Using JavaScript

A binary tree data structure is a tree data structure where each element has at most 2 children. This data structure will consist of three primary elements:

1. The data
2. A pointer to the left child
3. A pointer to the right child

A binary search tree is a binary tree data structure, based on nodes, that has specific properties that allow for operations such as searching and finding maximum or minimum values in a more efficient manner. The properties are as followed:

• The left child, and subsequently the left subtree, of a node contains only nodes with keys less than the node’s key
• The right child, and subsequently the right subtree, of a node contains only nodes with keys greater than the node’s key
• The subtrees must be binary search trees as well
• There are no duplicate nodes

In layman’s terms, starting at the top of the tree (root), the left child will be less than the root, while the right child will be greater than the root. Because of this, the right subtree of a node will only contain keys less than that of the node and vice versa for the left subtree.

Say a binary tree node was defined as such:

Given the binary tree and a value, to insert the value, we have to start at the root of the tree. We grab the value of the root and save it to a variable to check with the given value.

Using a while loop, we will traverse the tree, checking the value with the value of the current node. If the value is greater than the node, we check to see if the right child of the node exists. If it does not exist, we create a new node that is a right child of the current node. If a right child exist, we set the ‘current’ value to be the current node’s value that we are on and keep on traversing the tree. The same process will be true if the value is smaller than the node, except now we will check the left child instead.

The while loop will break once the new node is created and the current value will be the same as the given value. Here is the function in full:

A different implementation that involves recursion is also possible:

The logic is the same, but instead of saving the current node that we are on to a variable, we simply call the function again and pass the node and the value we would like to insert.