Binary Search Tree Algorithm Tutorial for JavaScript Beginners

In this article, I will try my best to explain some of the core algorithms that you should learn before a coding interview.

What is a Binary Search Tree (BST)?

Commonly seen in coding interviews, a BST is a tree-like data structure with a root at the top. They are a great way to store numerical values ​​because their ordered nature allows for fast searching and lookups.

Compared with ordinary trees, BST has the following characteristics:

• Each left child has a value less than its parent
• Each right child has a value greater than its parent
• Each node can contain 0 to 2 child nodes.

The following diagram should make things clearer.

Definition of a binary tree node

We usually define a binary tree node in Javascript with the following function:

 function TreeNode(val, left, right) {
     this.val = val
     this.left = left
     this.right = right
 }

Basic traversal of a binary tree (in-order, post-order, pre-order)

First, we need to know how to traverse each node of the BST. This allows us to execute a function on all nodes of the BST. For example, if we want to find a value x in a BST, we need nodes.

There are three main ways to do this. Fortunately, they share a common theme.

In-order traversal

A recursive algorithm is the simplest way to get started with in-order traversal of a binary tree. The idea is as follows:

• If the node is empty, do nothing - otherwise, recursively call the function on the left child of the node.
• Then, after traversing all left child nodes, perform some operations on the nodes. Our current node is guaranteed to be the leftmost node.
• Finally, the function on node.right is called.

The Inorder algorithm traverses the tree nodes from left, center, and right.

const inorder = (root) => {
    const nodes = []
    if (root) {
        inorder(root.left)
        nodes.push(root.val)
        inorder(root.right)
    }
    return nodes
}
// For our example tree, this will return [1,2,3,4,5,6]

Post-order traversal

A recursive algorithm is the simplest way to start a post-order traversal.

• If the node is empty, do nothing - otherwise, recursively call the function on the left child of the node.
• When there are no more left children, call the function on node.right.
• Finally, do some operations on the node.

Post-order traversal visits tree nodes from left, right, and center.

const postorder = (root) => {
    const nodes = []
    if (root) {
        postorder(root.left)
        postorder(root.right)
        nodes.push(root.val)
    }
    return nodes
}
// For our example tree, this will return [1,3,2,6,5,4]

Pre-order traversal

The simplest way to start a pre-order traversal is with a recursive algorithm.

• If the node is empty, do nothing - otherwise, do something on the node.
• Traverse the left children of a node and repeat.
• Traverse to the right child of the node and repeat.

Post-order traversal visits tree nodes from the center, left, and right.

const preorder = (root) => {
    const nodes = []
    if (root) {
        nodes.push(root.val)
        preorder(root.left)
        preorder(root.right)
    }
    return nodes
}
// For our example tree, this will return [4,2,1,3,5,6]

What is a valid binary search tree?

A valid binary search tree (BST) has all left children whose values ​​are less than the parent node, and all right children whose values ​​are greater than the parent node.
To verify whether a tree is a valid binary search tree:

• Defines the minimum and maximum value that the current node can have
• If the node's value is not within these ranges, it returns false
• Recursively verify the left child of the node, with the maximum bound set to the value of the node
• Recursively verify the right child of the node, with the minimum bound set to the value of the node

const isValidBST = (root) => {
    const helper = (node, min, max) => {
        if (!node) return true
        if (node.val <= min || node.val >= max) return false
        return helper(node.left, min, node.val) && helper(node.right, node.val, max)
    }
    return helper(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
}

How to find the maximum depth of a binary tree

Here, the algorithm tries to find the height/depth of our BST. In other words, we are looking at how many "levels" the BST contains.

• If the node is empty, we return 0 since it does not add any depth
• Otherwise, we add + 1 to our current depth (we traversed one level)
• Recursively calculate the depth of a node's children and return the maximum sum between node.left and node.right

const maxDepth = function(root) {
    const calc = (node) => {
        if (!node) return 0
        return Math.max(1 + calc(node.left), 1 + calc(node.right))
    }
    return calc(root)
};

How to find the least common ancestor between two tree nodes

Let's increase the difficulty. How do we find the common ancestor between two tree nodes in our binary tree? Let’s look at some examples.

In this tree, the lowest common ancestor of 3 and 1 is 2. The LCA of 3 and 2 is 2. The LCA of 6 and 1 and 6 is 4.

See the pattern here? The LCA between two tree nodes is either one of the nodes itself (cases 3 and 2), or a parent node where the first child is somewhere in its left subtree and the second child is somewhere in its right subtree.

The algorithm for finding the lowest common ancestor (LCA) between two tree nodes p and q is as follows:

• Verify if p or q is found in the left or right subtree
• Then, verify whether the current node is p or q
• If we find one of p or q in the left or right subtree, and one of p or q is the node itself, we have found the LCA
• If we find both p and q in the left or right subtree, we have found LCA

const lowestCommonAncestor = function(root, p, q) {
    let lca = null
    const isCommonPath = (node) => {
        if (!node) return false
        var isLeft = isCommonPath(node.left)
        var isRight = isCommonPath(node.right)
        var isMid = node == p || node == q
        if (isMid && isLeft || isMid && isRight || isLeft && isRight) {
            lca = node
        }
        return isLeft || isRight || isMid
    }
    isCommonPath(root)
    return lca
};

😊 Ending

So far, we have learned how to traverse, verify, and calculate the depth of a BST.

This concludes this article on the binary search tree algorithm tutorial for JavaScript beginners. For more relevant JavaScript binary search tree algorithm content, please search 123WORDPRESS.COM's previous articles or continue to browse the following related articles. I hope everyone will support 123WORDPRESS.COM in the future!