二叉搜索树有很多别名如：排序二叉树、二叉查找树等。

特点

它的特点：

左子树所有节点的值都小于等于根节点的值，右子树所有节点的值都大于等于根节点的值，并且每一颗子树都满足左孩子 <= 跟节点 <= 右孩子。
中序遍历的话值是一个从小到大的有序数组。

下面是一颗二叉搜索树，可以看下是否符合上面的特性。

基于二叉搜索树的特点可以让我们在操作树的时候提升很多效率。比如我们在普通树中查找一个元素，需要遍历整棵树：

function search(root, val) {
    if (!root) return null;
    if (root.val === val) return root;
    const left = search(root.left, val);
    const right = search(root.right, val);
    return left ? left : right;
}

但如果是二叉搜索树的话我们只需要遍历一边即可，并不用去遍历整棵树。

基本操作

查找某个值

在二叉搜索树中查找所需的最大次数等同于二叉树的高度。

function search(root, val) {
  if (!root) return root;
  if (root.val == val){
      console.log(root);
  }else if (root.val > val) {
      search(root.left, val)
  }else if (root.val < val) {
      search(root.right, val);
  }
}

插入新节点

function insertToBST(root, val) {
    if (!root) return (root = new TreeNode(val));
    if (root.val > val) {
        root.left = insertToBST(root.left, val);
    } else {
        root.right = insertToBST(root.right, val);
    }
    return root;
}

删除指定节点

function deleteNode(root, key) {
  if (!root) return null;
  if (root.val === key) {
      if (!root.left) return root.right;
      if (!root.right) return root.left;
      let node = root.right;
      while (node.left) {
          node = node.left;
      }
      node.left = root.left;
      root = root.right;
  }else if (root.val > key) {
      root.left = deleteNode(root.left, key);
  }else {
      root.right = deleteNode(root.right, key);
  }
  return root;
}

小册练习

450.删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。
示例 1:
输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。
示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
示例 3:
输入: root = [], key = 0
输出: []
提示:
节点数的范围 [0, 104].
-105 <= Node.val <= 105
节点值唯一
root 是合法的二叉搜索树
-105 <= key <= 105
进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-node-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var deleteNode = function (root, key) {
    if (!root) return null;
    if (root.val === key) {
        if (!root.left) return root.right;
        if (!root.right) return root.left;

        let node = root.right;
        while (node.left) {
            node = node.left;
        }
        node.left = root.left;
        root = root.right;

    }else if (root.val > key) {
        root.left = deleteNode(root.left, key);
    }else {
        root.right = deleteNode(root.right, key);
    }
    return root;
};

700.二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

例如，

给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和值: 2
你应该返回如下子树:

      2     
     / \   
    1   3
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。



来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var searchBST = function(root, val) {
    if (!root)  return root;
    if (root.val === val) {
        return root;
    }else if (root.val > val) {
        root = searchBST(root.left, val)
    }else {
        root = searchBST(root.right, val);
    }
    return root;
};

701.二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。



示例 1：


输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]
示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]




提示：

给定的树上的节点数介于 0 和 10^4 之间
每个节点都有一个唯一整数值，取值范围从 0 到 10^8
-10^8 <= val <= 10^8
新值和原始二叉搜索树中的任意节点值都不同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var insertIntoBST = function(root, val) {
    if (!root) return new TreeNode(val);
    if (root.val > val) {
        root.left = insertIntoBST(root.left, val);
    }else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
};