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

  • Is larger than any node in the left subtree.
  • Is smaller than any node in the right subtree.

Because of the binary search tree, we can use the algorithm more efficiently.

Intensive reading

Remember the recent great-great-grandfather problem of binary trees mentioned in Algorithms: 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 nearest common ancestor of the two specified nodes in the tree.

The nearest common ancestor in Baidu Encyclopedia is defined as: “For two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, which satisfies that X is the ancestor of P and Q and the depth of X is as large as possible (a node can also be its own ancestor).”

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

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

  1. ifp qIf the two nodes are located to the left or right of the current node, the current node meets the requirements.
  2. ifp qValues one greater than and one less than the current node, indicatingp qDistributed on the left and right sides of the current node.

Based on the above considerations, you can judge only by the value size, so the problem is simplified.

Next let’s look at an entry question, that is, how to verify a binary tree is a binary search tree.

Verify the binary search tree

A binary search tree is a binary search tree.

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 smaller than the current node.
  • The right subtree of a node contains only numbers greater than the current node.
  • All left and right subtrees must be binary search trees themselves.

This problem looks like it should be implemented with a very elegant recursion.

The most important thing about binary search tree is the limit of node value. If we can properly lock the value of each node, we can judge.

How do you tell if the node value is correct? If we start with the root node and assume the root node value is x, then the value of the node in the left tree must be less than x. If we go further to the left, then the value of the node in the left tree must be less than (assuming the first left node value is x1). X1.

function isValidBST(node: TreeNode, min = -Infinity, Max = Infinity) {if (node = = = null) return true / / judgment value range is reasonable if (node. Val < min | | node. Val > Max) return false / / Continuing the recursion, and specific to the binary search tree, Further narrowing the scope of maximum and minimum values of lock in return / / Max left subtree value for the current node values isValidBST (node. Left, min, &&} isValidBst (node.right, node.val, Max) &&} isValidBst (node.right, node.val, Max) &&}

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

Deletes 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 key, delete the node corresponding to the 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 that may be updated.

In general, removing a node can be divided into two steps:

  1. First, find the node that needs to be removed.
  2. If found, delete it.

Description: The time complexity of the algorithm is O(H), and H is the height of the tree.

To delete the node of the binary search tree, it is not difficult to find the node itself, because if the value is small, it is found from the left subtree; If the value is larger, you look for it from the right subtree, which itself is very easy to find. The challenge is, how do you ensure that the tree is still a binary search tree when you delete the element?

So let’s say we’re deleting a leaf, and obviously a binary search tree any subtree is a binary search tree, and we’re not breaking any of the other nodes, so we can just delete it, which is the easiest thing.

If you are not deleting a leaf node, who is going to replace it? So they’re asking for O(h), which is obviously not a good way to reconstruct it, so we need to think about it carefully.

If the deleted node exists on the right node, then it must find a replacement value from the right node and move it up. Who do you want? Find the minimum value of the right node, the minimum value is easy to find, after finding the replacement, equivalent to the problem to delete the minimum node, recursion is done.

If the deleted node has a left node, but no right node, then find a maximum replacement from the left node, and recursively delete the found node.

As can be seen, delete the binary search tree. In order to keep the properties of the binary search tree unchanged, recursive deletion nodes of repeated subproblems are needed continuously.

When you master the binary search tree characteristics, you can try to construct a binary search tree, the following is a let you arbitrarily construct a binary search tree topic: different binary search trees.

Different binary search trees

A binary search tree is a binary search tree. A binary search tree is a binary search tree

I’ll give you an integer
n, by
nAnd the node value is from
1 到
nnonidentical
Binary search treeHow many kinds are there? Returns the number of binary search trees that satisfy the problem.

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

You have to think of all the possibilities as how many combinations can you make of the left and right subtrees once you’ve determined the root node?

So for example, if n is equal to 10, so these 10 nodes, let’s say I take the third node as the root node, so the left subtree has two nodes, the right subtree has seven nodes, this combination would be DP(2) times DP(7), Suppose DP(n) represents the number of N nodes that can form any binary search tree.

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

So the answer is, 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]
}

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

The KTH largest node of the binary search tree

The KTH largest node of a binary search tree is a simple question. The question is as follows:

Given a binary search tree, find the number
kLarge nodes.

The reason why this problem is simple is that the middle order traversal of the binary search tree is from small to large, so as long as we traverse in reverse order, we can find the KTH largest node.

Traversal in reverse order, that is, right, root, left.

So that’s the problem.

conclusion

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

But through the above several examples can be found, only familiar with the characteristics of binary search tree is not enough, some problems need to be combined with the binary tree in order traversal, common ancestor characteristics and other common algorithm ideas to solve, so learn to integrate is very important.

The address for discussion is:
Intensive reading of Algorithms – Binary Search Trees Issue #337 DT-FE/Weekly

If you want to join the discussion, pleaseClick here toEvery week, a new theme will be released on weekends or Mondays. Front-end Intensive Reading – helps you filter reliable content.

Focus on
Front end intensive reading WeChat public number

<img width=200 src=”https://img.alicdn.com/tfs/TB165W0MCzqK1RjSZFLXXcn2XXa-258-258.jpg”>

Copyright Notice: Free Reprint – Non-commercial – Non-derivative – Keep your name (
Creative Commons 3.0 license)