insert-into-a-binary-search-tree

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given the <code>root</code> node of a binary search tree (BST) and a <code>value</code> to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice&nbsp;that there may exist&nbsp;multiple valid ways for the&nbsp;insertion, as long as the tree remains a BST after insertion. You can return any of them.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/05/insertbst.jpg" style="width: 752px; height: 221px;" />
<pre>
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/05/bst.jpg" style="width: 352px; height: 301px;" />
</pre>

Example 2:

<pre>
Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]
</pre>

Example 3:

<pre>
Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in&nbsp;the tree will be in the range <code>[0,&nbsp;104]</code>.</li>
	<li><code>-108 &lt;= Node.val &lt;= 108</code></li>
	<li>All the values <code>Node.val</code> are unique.</li>
	<li><code>-108 &lt;= val &lt;= 108</code></li>
	<li>It&#39;s guaranteed that <code>val</code> does not exist in the original BST.</li>
</ul>

insertIntoBST

Insert into a Binary Search Tree

Search in a Binary Search Tree

search-in-a-binary-search-tree

二叉搜索树中的搜索

Tree

Binary Search Tree

Binary Tree

给定二叉搜索树（BST）的根节点<meta charset="UTF-8" />&nbsp;<code>root</code>&nbsp;和要插入树中的值<meta charset="UTF-8" />&nbsp;<code>value</code>&nbsp;，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

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

&nbsp;

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/05/insertbst.jpg" />
<pre>
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/05/bst.jpg" />
</pre>

示例 2：

<pre>
输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]
</pre>

示例 3：

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

&nbsp;

提示：

<ul>
	<li>树中的节点数将在<meta charset="UTF-8" />&nbsp;<code>[0,&nbsp;104]</code>的范围内。<meta charset="UTF-8" /></li>
	<li><code>-108&nbsp;&lt;= Node.val &lt;= 108</code></li>
	<li>所有值&nbsp;<meta charset="UTF-8" /><code>Node.val</code>&nbsp;是&nbsp;独一无二&nbsp;的。</li>
	<li><code>-108&nbsp;&lt;= val &lt;= 108</code></li>
	<li>保证&nbsp;<code>val</code>&nbsp;在原始BST中不存在。</li>
</ul>