Shulou(Shulou.com)06/01 Report--

This article mainly introduces how to use JavaScript to achieve binary search tree algorithm, has a certain reference value, interested friends can refer to, I hope you can learn a lot after reading this article, let the editor take you to understand it.

What is a binary search tree (BST)?

It is common in coding interviews that BST (Binary search tree) is a tree data structure with a root at the top. They are a good way to store values because their ordered nature allows for quick search and lookup.

Compared with a normal tree, BST has the following characteristics:

The value of each left child is smaller than that of his parents.

Every child on the right is worth more than his parents.

Each node can contain 0 to 2 child nodes.

The picture below should illustrate things more clearly.

The definition of binary tree node

We usually define a binary tree node in Javascript. The function is as follows:

Function TreeNode (val, left, right) {this.val = val this.left = left this.right = right} binary tree basic traversal (middle order, post order, pre order)

The first thing to know is 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 to find a value in BST, we need a node.

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

Mid-order traversal

A recursive algorithm is the easiest way to start using order traversal in a binary tree. The ideas are as follows:

If the node is empty, nothing is done-- otherwise, the function on the node's left child node is called recursively.

Then, after traversing all the left child nodes, do 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 the left, middle, and right.

/ * * @ param {TreeNode} root*/const inorder = (root) = > {const nodes = [] if (root) {inorder (root.left) nodes.push (root.val) inorder (root.right)} return nodes} / / for our example tree, this returns

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

If the node is empty, nothing is done-- otherwise, the function on the node's left child node is called recursively.

When there are no more left children, call the function on node.right.

Finally, do something on the node.

Traversal accesses the tree node from left, right, and middle.

/ * * @ param {TreeNode} root*/const postorder = (root) = > {const nodes = [] if (root) {postorder (root.left) postorder (root.right) nodes.push (root.val)} return nodes} / / for our example tree, this returns preface traversal

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

If the node is empty, do nothing-- otherwise, do something on the node.

Iterate through the left child of the node and repeat.

Traverse to the right child of the node and repeat.

Traverse the middle, left, and right access tree nodes in the following order.

/ * * @ param {TreeNode} root*/const preorder = (root) = > {const nodes = [] if (root) {nodes.push (root.val) preorder (root.left) preorder (root.right)} return nodes} / / for our example tree, this returns, what is an effective binary search tree?

A valid binary search tree (BST) has all left child nodes whose values are less than the parent node, and all right child nodes whose values are greater than the parent node.

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

Define the minimum and maximum values that the current node can have

If the value of the node is not in these ranges, false is returned

Recursively verify the left child of the node, and the maximum boundary is set to the value of the node

Recursively verify the right child of the node, and the minimum boundary is set to the value of the node

/ * * @ param {TreeNode} root*/const isValidBST = (root) = > {const helper = (node, min, max) = > {if (! node) return true if (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 the 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 does not add any depth

Otherwise, we add + 1 to our current depth (we traverse one layer)

Recursively calculates the depth of the node child and returns the maximum sum between node.left and node.right

/ * * @ param {TreeNode} root*/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 smallest common ancestor between two tree nodes

Let's make it more difficult. How do we find a 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 the two tree nodes is either one of the nodes themselves (in the case of 3 and 2) or the parent node, where the first child node is somewhere in its left child tree and the second child node is somewhere in its right child tree.

The algorithm for finding 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 we find one of p or Q in the left or right subtree, and one of p or Q is the node itself, we find LCA

If we find p and Q in either the left subtree or the right subtree, we find LCA

/ * * @ param {TreeNode} root* @ param {TreeNode} p* @ param {TreeNode} q*/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} | Thank you for reading this article carefully. I hope the article "how to use JavaScript to achieve binary search Tree algorithm" shared by the editor will be helpful to everyone. At the same time, I also hope that you will support and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.