The property of a binary search tree is that the value of any node:

  • Is greater than any node in the left subtree.
  • Is less than any node in the right subtree.

Because of the properties of binary search trees, we can apply algorithms more efficiently.

Intensive reading

Remember the nearest paternal ancestor of binary trees mentioned in Algorithm-Binary Trees? If this is a binary search tree, is there a smarter way to do it? You can pause and think about it.

The nearest common ancestor of a binary search tree

The nearest common ancestor of a binary search tree is a simple question with the following title:

Given a binary search tree, find the most recent common ancestor of two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu encyclopedia is: “For the two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, satisfying that X is the ancestor of P and Q and x is as deep as possible (a node can also be its own ancestor).

The first judgment condition is the same, that is, if the value of the current node is equal to either P or Q, the current node is its nearest common ancestor.

What if it’s not? Considering the characteristics of binary search tree and common ancestor, it can be found that:

  1. ifp qIf the two nodes are to the left or right of the current node, the current node meets the requirements.
  2. ifp qOne value is greater than the current node and the other is less than the current nodep qDistributed on the left and right sides of the current node.

With that in mind, you can tell just by the size of the value, so the problem is simplified.

Let’s look at an introductory problem, which is how to verify that a binary tree is a binary search tree.

Verify the binary search tree

Verifying binary search trees is an intermediate problem, with the following title:

Given a binary tree, determine whether it is a valid binary search tree.

Suppose a binary search tree has the following characteristics:

  • The left subtree of a node contains only numbers less than the current node.
  • The right subtree of a node only contains numbers greater than the current node.
  • All left and right subtrees must themselves also be binary search trees.

This problem looks like it should be done in a very elegant recursion.

The most important thing in binary search tree is the limit of node value. If we can correctly stick to the value of each node, we can judge it.

How do you determine if the node value is correct? We can recursively work backwards, that is, starting at the root, assuming that the root is x, the value of the left tree must be less than x, and going further to the left, the value of the left tree must be less than (assuming that the first left tree is x1) x1. The same is true for the right tree, so we can write the answer:

function isValidBST(node: TreeNode, min = -Infinity, max = Infinity) {
  if (node === null) return true
  // Check whether the value range is reasonable
  if (node.val < min || node.val > max) return false
  // Continue the recursion, and further narrow the maximum and minimum locking range according to the specific binary search tree
  return 
    // The left subtree value Max is the current node value
    isValidBST(node.left, min, node.val) &&
    // The right subtree value min is the current node value
    isValidBST(node.right, node.val, max) &&
}
Copy the code

Let’s look at some simple binary search tree operations, such as deleting nodes in a binary search tree.

Delete a node in the binary search tree

Delete a node from a binary search tree

Given the root node of a binary search tree root and a value of key, delete the nodes corresponding to key in the binary search tree and ensure that the properties of the binary search tree remain unchanged. Returns a reference to the root node of the binary search tree (which may be updated).

In general, node deletion can be divided into two steps:

  1. First find the node to delete;
  2. If found, delete it.

Note: The algorithm time complexity is O(h), h is the height of the tree.

To delete a node in a binary search tree, it is not difficult to find the node itself, because if the value is small, it is found in the left subtree; If the value is large, you look in the right subtree, which in itself is pretty easy to look up. The challenge is, how do you make sure that if you delete the element, this tree is still a binary search tree?

Let’s say we’re deleting a leaf node, and obviously any subtree of a binary search tree is a binary search tree, and we’re not breaking any of the other nodes, so we just delete it, the easiest thing to do.

If the node is not a leaf, who replaces it? So they’re asking for order h, and obviously you can’t reconstruct it, so we have to think about it carefully.

If the deleted node exists in the right node, then it must find a replacement value from the right node to move up. Who to look for? Find the minimum value of the right node ah, the minimum value is very easy to find, find the replacement, equivalent to the problem to delete the minimum value node, recursion is done.

Assume that the deleted node has a left node but no right node, then find a maximum replacement from the left node, and delete the found node recursively in the same way.

As can be seen, deleting the binary search tree, in order to keep the properties of the binary search tree unchanged, it is necessary to constantly perform recursive deletion nodes of repeated subproblems.

Once you have mastered the binary search tree feature, you can try to construct a binary search tree, the following is a topic that allows you to construct any binary search tree: different binary search trees.

Different binary search trees

Different binary search trees is an intermediate problem, with the following title:

Given an integer n, how many binary search trees are composed of exactly n nodes with different values from 1 to n? Returns the number of binary search tree species that satisfy the problem.

This problem focuses on the combination of dynamic programming thinking + Cartesian product thinking.

You need to think of all the possibilities as how many ways can the left and right subtrees be combined once the root node is identified?

For example, if n is equal to 10, then these 10 nodes, if I take the third node as the root node, then the left subtree has two nodes, the right subtree has seven nodes, and the combination is DP of 2 times DP of 7, Assume that DP(n) represents the number of n nodes that can form any binary search tree.

This is only the case when the third node is the root node. In fact, each node as the root node is a different tree (axisymmetric is also different), so we need to calculate from the first node to the NTH node.

So the answer is there, let’s take the special case DP(0)=1, DP(1)=1, so:

function numTrees(n: number) {
  const dp: number[] = [1.1]

  for (let i = 2; i <= n; i++) {
    for (let j = 1; j <= i; j++) {
      dp[i] += dp[j - 1] * dp[i - j]
    }
  }

  return dp[n]
}
Copy the code

And finally, let’s do a value finding problem, not to find the maximum, but to find the KTH maximum.

The KTH largest node of a binary search tree

The KTH node of a binary search tree is a simple problem, which is as follows:

Given a binary search tree, find the KTH largest node.

This problem is easy because the middle order traversal of a binary search tree is from small to large, so you can find the KTH largest node by reverse middle order traversal.

Reverse order in order traversal, that is, right, root, left.

And we’re done.

conclusion

The characteristic of binary search tree is very simple, that is, the root node value is sandwiched between the left and right subtrees, which can solve almost all related problems.

However, through the above examples, it can be found that it is not enough to be familiar with the characteristics of binary search tree. Some problems need to be combined with general algorithm ideas such as sequence traversal and common ancestor features in binary tree to solve them. Therefore, it is important to learn to master them thoroughly.

The discussion address is: intensive reading algorithm-Binary Search Tree · Issue #337 · dT-fe /weekly

If you’d like to participate in the discussion, pleaseClick here to, with a new theme every week, released on weekends or Mondays. Front end Intensive Reading – Helps you filter the right content.

Pay attention to the front end of intensive reading wechat public account

Copyright Notice: Freely reproduced – Non-commercial – Non-derivative – Remain signed (Creative Commons 3.0 License)