First of all, we need to understand the properties of binary search trees:

  1. forBSTEach node ofnode, the value of the left subtree node is greater thannodeThe right subtree is smaller than the right subtreenodeThe value of the big.
  2. forBSTEach node ofnodeIt’s on the left and on the rightBST

It is important to note that, from the point of view of brush algorithm, there is another important property: the middle-order traversal of BST is ordered (ascending).

So let’s get started. I’m sorry I’ve been putting it off lately.

230. The KTH smallest element in a binary search tree

So if you think about it this way, and you have an ascending sequence, then you have the KTH small element 1,2,3,4,5 where is the first small element? That’s just one, just by virtue of the order traversal in BST. Isn’t that a coincidence?

Code implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : Right) *} */ ** * @param {TreeNode} root * @param {number} k * @return {number} */ Var kthunit = function(root, k) {var kthunit = function(root, k) { Let count = 0; Function traverse(root, k) {// base case if (root === null) return traverse(root.left, k); if (count === k) { res = root.val; return res; } traverse(root.right, k)} // traverse(root, k) return res; }Copy the code

538. Convert a binary search tree to a summation tree

Thinking to comb

In fact, this problem requires a reverse idea, BST middle order traversal is in ascending order, what if we modify it a little bit?

Function traverse(root) {traverse(root.left) {traverse(root.left)} traverse(root)Copy the code

Would it be better to iterate and sum from 8, the right subtree, to the right, middle and left, by thinking backwards? You can think about that, and take a closer look at the instance tree:

Code implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : Right) *} */ /** * @param {TreeNode} root * @return {TreeNode} */ var convertBST = function(root) {// ascending to descending // sum Let sum = 0; Function traverse(root) {// base case if (root === null) return traverse(root.right) // maintain sum += root.val; root.val = sum; traverse(root.left) } traverse(root) return root; }Copy the code

1038. From search tree to larger sum tree

Thinking to comb

This problem is exactly the same as the previous problem and I won’t go over it here

Code implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : // ** * @param {TreeNode} root * @return {TreeNode} */ var bstToGst = function(root) {// record the sum and let  sum = 0; function traverse(root) { if (root === null) return; Traverse (root.right) // sum += root.val; root.val = sum; traverse(root.left) } traverse(root) return root; }Copy the code

654. Maximum binary tree

Thinking to comb

The key to building a binary tree is to find the root node, the root node. Then we need to iterate to find the largest value in the array, maxVal, and root. You can recurse the arrays to the left and right of maxVal as the left and right subtrees of root

/ / var constructMaximumBinaryTree pseudo code = function (,2,1,6,0,5 [3]) {/ / find the array maximum let root = TreeNode (6) let root. Left = ConstructMaximumBinaryTree ([3, 2, 1]) let root. The right = constructMaximumBinaryTree ([0, 5)) return the root; }Copy the code

Here we need to pay attention to how to construct a recursive function: what are the parameters required? Because we need to separate the left subtree from the right subtree we need to keep checking where the subtree starts and ends

function build (nums, start, end) { // base case if (left > right) return; let maxValue = -1, index = -1; // find for (let I = start; i < end; i++) { if (nums[i] > maxValue) { maxValue = nums[i]; index = i; }} // Create tree root; let root = new TreeNode(maxValue); Root. left = build(nums, start, index - 1) root.left = build(nums, index + 1, end) root.right = build(nums, index + 1, end) }Copy the code

Here is actually the core code that we have written out of this problem, and we need to put it together patiently

Code implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {number[]} nums * @return {TreeNode} */ var constructMaximumBinaryTree = function(nums) { let  root = build(nums, 0, nums.length-1) return root; } function build(nums, start, end) { // base case if (left > right) return; let maxVal = -1, index = -1; for (let i = start; i < end; i++) { if (nums[i] > maxVal) { maxVal = nums[i] index = i; }} let root = new TreeNode(maxVal) root.left = build(nums, start, index - 1) root.right = build(nums, index + 1, end) return root; }Copy the code

98. Validate binary search trees

Thought analysis

BST similar code logic is to take advantage of the small on the left and large on the right

function BST(root, Target) {if (root.val === target) {if (root.val < target) {// if (root.val < target) {// BST(root.right, Target)} if (root.val > target) {// BST(root.left, target)}}Copy the code

So there are a few things we need to pay attention to when we go to verify that a tree is legitimate:

  1. For each noderootEach code value needs to check that its left and right child nodes are smaller than the other
  2. fromBSTFrom the definition of,rootThe entire left subtree of PI is going to be less thanroot.valThe whole right subtree is going to be greater thanroot.val

However, a problem arises, that is, for a node, it can only manage its left and right child nodes, how to transfer the constraint relationship to the left and right subtrees?

left.val < root.val < right.val

Can we use this relationship to restrain them?

The definition of the main function

function isValidBST(root, null, null)

Copy the code

For left subtrees, every left subtree val needs to satisfy min.val < val < root.val

isValidBST(root.left, min, root) 
Copy the code

Similarly, val for every right subtree should satisfy root.val < val < max.val

isValidBST(root.right, root, max)
Copy the code

Code implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {boolean} */ var isValidBST = function(root) { return isValid(root, Null, null)} function isValid(root, min, Max) { If (root === null) return true; If (min! == null && root.val <= min.val) return false; // Bigger than the biggest. If (Max! == null && root.val >= max.val) return false; return isvalid(root.left, min, root) && isValid(root.right, root, max) }Copy the code

700. Search in binary search tree

Thought analysis

In fact, does it look like the binary tree thinking template we mentioned above? So what they’re asking is to find the node that corresponds to val, and return the subtree with that node as the root, which is essentially just return the current node with a subtree with that node as the root.

Code implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
 
 var searchBST = function(root, val) {
     // base case 
     if (root === null) return null;
     
     if (root.val === val) {
        return root;
     }
     
     if (root.val < val) {
       searchBST(root.right)
     }
     if (root.val > val) {
       searchBST(root.left)
     }

 }

Copy the code

701. Insert operations in binary search trees

Thought analysis

One thing to notice here is that you how do you insert? If it is target === val, it means that the position is not empty, so it cannot be inserted. Therefore, the position we want to insert must be an empty position. If you carefully analyze this process, do you have a new understanding of the base case? This is it

Code implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} val * @return {TreeNode} */ var insertIntoBST = function(root, Val) {// base case if (root === null) // Insert return new TreeNode(val) // if (root === val) insertIntoBST(root.right) } if (root.val > val) { insertIntoBST(root.left) } }Copy the code

450. Delete nodes in the binary search tree

Thought analysis

Start with a basic template:

Var deleteNode = function(root, key) {if (root === null) return null; If (root.val === key) {// Delete operation} if (root.val < key) {deleteNode(root.right, val) } if (root.val > key) { deleteNode(root.left, val) } }Copy the code

When root.val === key, we need to perform a delete logic

Case1: No children

if (root.left === null && root.right) reture null;
Copy the code

Case2: if there is only one non-empty node, this non-empty node is required to take its place

if (root.left === null) return root.right;
if (root.right === null) return root.left;
Copy the code

Case3: If there are two nodes, we need to replace the largest element in the left subtree or the smallest element in the right subtree. We use the second method

if (root.left ! == null && root.right ! == null) {let minNode = getMin(root.right) // Replace the current value with the smallest value root.val = minNode; Root. right = deleteNode(root.right, minnode.val)} root.right = deleteNode(root.right, minnode.val)}Copy the code

Gets the smallest element in the right subtree

Function getMin(node) {while (node.left! == null) continue to find the following left subtree node = node.left; return node; // Not found and front-end prototype chain seems ah}Copy the code

Code implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} key * @return {TreeNode} */ var deleteNode = function(root, Key) {// Basic copy if (root === null) return null; If (root.val === key) {// Delete operation // case1, 2 if (root.left === null) return root.right; if (root.right === null) return root.left; // case 3 let minNode = getMin(root.right); root.val = minNode.val; // add root.right = deleteNode(root.right, minNode); If (root.val < key) {deleteNode(root.right, val)} if (root.val > key) {deleteNode(root.left, val) val) } function getMin(node) { while(node.left ! == null) node = node.left; return node; }}Copy the code