#701

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Insert into a Binary Search Tree

Insert a value into a Binary Search Tree while maintaining the BST properties, focusing on tree traversal and state tracking.

tree binary search tree binary tree

Problem Statement

You are given the root node of a Binary Search Tree (BST) and a value to insert into the tree. The value should be inserted into the tree such that the tree remains a valid BST after the insertion. It's guaranteed that the value does not already exist in the tree.

There can be multiple valid insertion points for the value as long as the tree structure remains valid. Your task is to return the root node of the BST after the insertion of the given value.

Examples

Example 1

Input: root = [4,2,7,1,3], val = 5

Output: [4,2,7,1,3,5]

Another accepted tree is:

Example 2

Input: root = [40,20,60,10,30,50,70], val = 25

Output: [40,20,60,10,30,50,70,null,null,25]

Example details omitted.

Example 3

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5

Output: [4,2,7,1,3,5]

Example details omitted.

Constraints

The number of nodes in the tree will be in the range [0, 104].
-108 <= Node.val <= 108
All the values Node.val are unique.
-108 <= val <= 108
It's guaranteed that val does not exist in the original BST.

Solution Approach

Recursive Insertion

In this approach, start at the root and recursively traverse down the tree. At each node, compare the given value with the current node's value. If the value is smaller, move to the left child; if larger, move to the right. When you reach a null spot, insert the new value at that location.

Iterative Insertion

In this approach, use an iterative method to find the appropriate insertion point. Start at the root and move down the tree iteratively, comparing values until you find a null spot. Insert the new value at that spot once the correct child position is found.

Balanced Tree Considerations

While the problem guarantees that the new value does not exist in the BST, it does not explicitly address balancing. For practical applications, consider whether the tree needs balancing to ensure efficient future operations. Though this isn't required in the problem, it can be useful in real-world scenarios.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of both the recursive and iterative approaches is O(h), where h is the height of the tree. In the worst case, this could be O(n) for an unbalanced tree. The space complexity is O(h) for recursive calls, or O(1) for the iterative approach when no extra space is used.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Recursion

If the root node is null, we directly create a new node with the value $\textit{val}$ and return it.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

# 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

Continue Practicing

#700 search in a binary search tree #703 kth largest element in a stream #669 trim a binary search tree