This is the 12th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

In this article, I’ll try to explain some of the core algorithms you should learn before coding interviews.

What is binary search tree (BST)?

Common in coding interviews, a BST is a tree-like data structure with a root at the top. They are a good way to store numbers because their ordered nature allows for quick searches and lookups.

Compared to ordinary trees, BST has the following features:

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

The chart below should make things clearer.

Definition of binary tree nodes

We usually define a binary tree node in Javascript as follows:

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

Binary tree basic traversal (middle order, posterior order, anterior order)

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

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

In the sequence traversal

Recursive algorithms are the easiest way to start using ordered traversal in binary trees. The idea is as follows:

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

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, return [1,2,3,4,5,6]
Copy the code

After the sequence traversal

A recursive algorithm is the easiest way to start a sequential traversal.

  • If the node is empty, nothing is done — otherwise, the function on the left child node of the node is recursively called.
  • When there are no more left children, call the function on Node.right.
  • Finally, do something on the node.

Post-order traversal accesses 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, return [1,3,2,6,5,4]
Copy the code

The former sequence traversal

A recursive algorithm is the easiest way to start a preorder traversal.

  • If the node is empty, do nothing — otherwise, do something on the node.
  • The left child node of the node is traversed and repeated.
  • Iterate to the right child of the node and repeat.

The sequential traversal accesses 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, return [4,2,1,3,5,6]
Copy the code

What is an effective binary search tree?

A valid binary search tree (BST) has all left children whose value is less than the parent, and all right children whose value is greater than the parent.

To verify that a tree is a valid binary search tree:

  • Defines the minimum and maximum values that the current node can have
  • If the value of the node is outside of these ranges, false is returned
  • The left child of the node is recursively validated, with the maximum boundary set to the value of the node
  • Recursively verify the right child of the node, with the minimum boundary 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)
}
Copy the code

How to find the maximum depth of binary tree

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

  • If the node is empty, we return 0 because it doesn’t add any depth
  • Otherwise, we add + 1 to our current depth (we iterate through one layer)
  • Recursively calculates the depth of node nodes and returns 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)
};
Copy the code

How do I find the minimum common ancestor between two tree nodes

Let’s make it harder. 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 (in the case of 3 and 2) or a parent node, where the first child is located somewhere in its left subtree and the second child is located somewhere in its right subtree.

The algorithm to find the lowest common ancestor (LCA) between two tree nodes P and Q is as follows:

  • Verify that p or Q is found in the left or right subtree
  • Then, verify whether the current node is P or q
  • If one of p or q is found in the left or right subtree, and one of p or Q is the node itself, we have found LCA
  • If we find p and Q in either the left subtree or the right subtree, we find 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
};
Copy the code

😊 end of want to say

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

These algorithms are often asked in coding interviews. It is important to understand them before practicing more advanced BST applications, such as finding the LCA of two nodes. I hope you enjoyed this article. If you like it, share it with your friends. Feel free to comment below and I’ll get back to you as soon as possible. 😉

I’ve been writing a technical blog for a long time, mostly through Nuggets, and this is my python basics tutorial. I like to share technology and happiness through articles. For more information, you can visit my blog: Gold Diggers – Sea People. Hope you like it!

If you do learn something new from this post, like it, bookmark it and share it with your friends. 🤗 Finally, don’t forget ❤ or 📑 for support