What is the time complexity of inserting a node into a Binary Search Tree?

The time complexity of inserting a node depends on the tree height. In the worst case, for an unbalanced tree, it is O(n), but for a balanced tree, it is O(log n).

How does the recursive approach differ from the iterative approach in BST insertion?

In the recursive approach, you use function calls to traverse the tree, while in the iterative approach, you manually traverse the tree using a loop. Both approaches have the same time complexity but differ in their space usage and ease of implementation.

Can the insertion operation cause a Binary Search Tree to become unbalanced?

While the insertion itself does not balance the tree, it can lead to an unbalanced tree if done repeatedly without any balancing strategy. This could impact future operations like search or insertion.

What should I do if the tree is empty?

If the tree is empty, simply create a new root node with the value to be inserted. The new node will be the root of the tree.

Can there be multiple correct answers for the insertion?

Yes, there can be multiple valid ways to insert the value into the tree, as long as the BST properties are maintained.

#701

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。 …

树二叉搜索树二叉树

题目描述

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

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

示例 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⁴]的范围内。
-10⁸ <= Node.val <= 10⁸
所有值 Node.val 是 独一无二 的。
-10⁸ <= val <= 10⁸
保证 val 在原始BST中不存在。

lightbulb

解题思路

方法一：递归

如果根节点为空，我们直接创建一个新节点，值为 $\textit{val}$ ，并返回。

如果根节点的值大于 $\textit{val}$ ，我们递归地将 $\textit{val}$ 插入到左子树中，并将左子树的根节点更新为返回后的根节点。

如果根节点的值小于 $\textit{val}$ ，我们递归地将 $\textit{val}$ 插入到右子树中，并将右子树的根节点更新为返回后的根节点。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是二叉树的节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return TreeNode(val)
        if root.val > val:
            root.left = self.insertIntoBST(root.left, val)
        else:
            root.right = self.insertIntoBST(root.right, val)
        return root

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate explain the difference between recursive and iterative approaches for tree traversal?
question_mark
Does the candidate consider tree balancing or assume the tree is balanced in all cases?
question_mark
Is the candidate able to identify and justify the time and space complexity for the given approaches?

warning

常见陷阱

外企场景

error
Forgetting to return the root of the tree after the insertion is complete.
error
Assuming that the tree is balanced without confirming or addressing balancing in the problem.
error
Inserting the value incorrectly by not respecting the binary search tree properties (left < root < right).

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the tree is a complete binary tree?
arrow_right_alt
How does the solution change if the tree is unbalanced?
arrow_right_alt
Can you handle cases where the tree is initially empty?

help

常见问题

外企场景

继续练习

#700 二叉搜索树中的搜索 #703 数据流中的第 K 大元素 #669 修剪二叉搜索树