Data structures — Binary Search Trees

An introduction to Binary Search Trees and some common methods for this data structure.

Example of a Binary Search Tree

What are Binary Search Trees?

Binary Search Trees is a type of data structure to store data in an ordered way. This data structure consists of nodes, and each node has at most two child nodes. The order of these nodes follow a property called the BST property. The BST property states that the value of a left child node is less than it’s parent, and the right child node is greater than it’s parent. This property allows for fast operations, to which most of them fall within O(log(n)).

An example of a binary search tree can be found above. The node at the top is called the root node because it does not have any parents. If you follow each node, you’ll see that they all follow the BST property.

Time Complexities of common operations in Binary Search Trees

• Search — Average: O(log(n)) Worst Case: O(n)
• Insert — Average: O(log(n)) Worst Case: O(n)
• Delete — Average: O(log(n)) Worst Case: O(n)

Search algorithms

There are many different ways to traverse a Binary Search Tree and they can be boiled down to three types: Post Order Traversal, In Order Traversal, Pre Order Traversal.

Pre Order Traversal (Depth First Search)

Pre order traversal is similar to Depth First Search so we’ll cover that first. Depth First Search goes deep first, checking all the child nodes in one sub-tree first, then moving to the other. This can be done iteratively or recursively. We’ll cover the iterative code here that’ll use a stack as an auxiliary data structure to navigate the an entire sub-tree before moving to the next.

depthFirstIterative = (root) => {
    let stack = [root];
    let res = [];
    while (stack.length !== 0) {
        let curr = stack.pop();
        res.push(curr.val);
        if (curr.right) stack.push(curr.right);
        if (curr.left) stack.push(curr.left);