LeetCode 701 - Insert into a Binary Search Tree

Difficulty: 🟡 Medium
Topics: Tree, Binary Search Tree, Binary Tree

Solution

Problem Understanding

This problem asks us to insert a new value into an existing Binary Search Tree, abbreviated as BST, while preserving the BST property.

A Binary Search Tree is a binary tree with a special ordering rule:

Every value in the left subtree of a node is smaller than the node’s value.
Every value in the right subtree of a node is larger than the node’s value.

You are given:

root, which is the root node of the BST
val, the integer value that must be inserted

Your task is to return the root of the updated BST after inserting the new value into the correct position.

The problem guarantees that:

All node values are unique
val does not already exist in the tree

This guarantee simplifies the logic because we never need to handle duplicates.

The insertion process follows the BST ordering rules. Starting from the root:

If val is smaller than the current node, move to the left child.
If val is larger than the current node, move to the right child.
Continue until an empty position (None or nil) is found.
Insert the new node there.

An important detail is that there may be multiple valid BST structures after insertion. This happens because some trees can be rearranged differently while still satisfying BST ordering. The problem accepts any valid BST.

The constraints tell us several important things:

The tree can contain up to 10^4 nodes, so an efficient traversal is preferred.
Node values may be large negative or positive integers, but standard integer types are sufficient.
Since the tree is already a BST, we should exploit that property instead of scanning the entire tree.

Several edge cases are important:

The tree may initially be empty.
The new value may become a leaf node deep in the tree.
The BST may be highly unbalanced, behaving like a linked list.
The inserted value may become the leftmost or rightmost node.

A naive implementation that ignores BST ordering would waste time exploring unnecessary branches.

Approaches

Brute Force Approach

A brute-force strategy would be to completely ignore the BST property. We could traverse every node in the tree until finding a valid empty location where the value could be inserted.

For example, we might perform a full DFS traversal and check possible insertion locations manually.

This approach works because eventually every node is examined, and a correct insertion point can be found. However, it is inefficient because the BST structure already provides directional information that tells us exactly where to go.

Instead of exploring both left and right subtrees at every node, we only need to follow one path.

In the worst case, the brute-force solution touches every node even when the insertion position is obvious early in the traversal.

Optimal Approach

The key observation is that BST ordering completely determines the insertion path.

At each node:

If val < node.val, the new value must belong somewhere in the left subtree.
If val > node.val, the new value must belong somewhere in the right subtree.

This means we never need to search both sides of the tree.

We simply walk downward from the root until we find a missing child position where the new node should be attached.

This produces an efficient solution because only one root-to-leaf path is traversed.

The implementation can be written either recursively or iteratively. The recursive version is concise and maps naturally to the BST definition.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Traverses the entire tree unnecessarily
Optimal	O(h)	O(h) recursive, O(1) iterative	Traverses only one BST path, where `h` is tree height

Algorithm Walkthrough

Recursive BST Insertion

Start at the root node.

The root is the current position where we decide whether the new value belongs in the left subtree or right subtree. 2. Check whether the current node is empty.

If the current node is None, this means we have reached the correct insertion location. Create and return a new node containing val. 3. Compare val with the current node’s value.

If val is smaller, the BST property guarantees the correct insertion position must exist somewhere in the left subtree. 4. Recursively insert into the left subtree.

Call the insertion function on root.left, then assign the returned subtree back to root.left. 5. Otherwise, insert into the right subtree.

Since duplicates are impossible, if val is not smaller, it must be larger. Recursively insert into root.right. 6. Return the current root.

After insertion is completed deeper in the tree, return the current node unchanged so parent links remain connected correctly.

Why it works

The algorithm works because at every node it preserves the BST invariant:

All left subtree values remain smaller than the node.
All right subtree values remain larger than the node.

The recursive search follows exactly the same path that a BST lookup would follow for the target value. When an empty position is found, inserting the node there maintains correct ordering throughout the tree.

Python Solution

# 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 val < root.val:
            root.left = self.insertIntoBST(root.left, val)
        else:
            root.right = self.insertIntoBST(root.right, val)

        return root

The implementation begins with the base case. If the current node is None, we have reached the insertion point, so a new TreeNode is created and returned.

Next, the code compares val with the current node’s value.

If the new value is smaller, recursion continues into the left subtree. The returned subtree root is reassigned to root.left. This reassignment is important because the recursive call may create a brand new node.

If the new value is larger, recursion proceeds into the right subtree in the same manner.

Finally, the current root is returned so the recursive calls reconnect properly while unwinding back to the original root.

The code directly mirrors the BST property, making it both concise and easy to reason about.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }

    if val < root.Val {
        root.Left = insertIntoBST(root.Left, val)
    } else {
        root.Right = insertIntoBST(root.Right, val)
    }

    return root
}

The Go implementation follows exactly the same recursive structure as the Python version.

The main difference is pointer handling. In Go, tree nodes are manipulated through pointers, so a new node is created using &TreeNode{Val: val}.

The nil keyword in Go serves the same purpose as None in Python.

Because Go uses explicit struct fields and pointers, subtree updates are written as:

root.Left = insertIntoBST(root.Left, val)

and similarly for the right subtree.

No special overflow handling is required because the problem constraints fit comfortably inside Go’s integer range.

Worked Examples

Example 1

Input:

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

Initial tree:

We insert 5.

Step	Current Node	Comparison	Action
1	4	5 > 4	Move right
2	7	5 < 7	Move left
3	None	insertion point	Create node 5

Updated tree:

Example 2

Input:

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

Initial tree:

          40
         /  \
       20    60
      / \   / \
    10  30 50 70

Insertion trace:

Step	Current Node	Comparison	Action
1	40	25 < 40	Move left
2	20	25 > 20	Move right
3	30	25 < 30	Move left
4	None	insertion point	Create node 25

Updated tree:

          40
         /  \
       20    60
      / \   / \
    10  30 50 70
        /
       25

Example 3

Input:

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

Traversal:

Step	Current Node	Comparison	Action
1	4	5 > 4	Move right
2	7	5 < 7	Move left
3	None	insertion point	Insert node

Final tree:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(h)	Only one root-to-leaf path is traversed
Space	O(h)	Recursive call stack depth equals tree height

The time complexity depends on the height of the tree.

In a balanced BST, the height is approximately log n, producing efficient insertion performance.

In the worst case, when the tree becomes completely skewed, the height becomes n, making the runtime O(n).

The recursive implementation also uses call stack space proportional to the tree height.

Test Cases

# Helper functions for testing

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, val):
        if root is None:
            return TreeNode(val)

        if val < root.val:
            root.left = self.insertIntoBST(root.left, val)
        else:
            root.right = self.insertIntoBST(root.right, val)

        return root

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Test 1: Empty tree insertion
root = None
root = Solution().insertIntoBST(root, 5)
assert inorder(root) == [5]  # inserting into empty BST

# Test 2: Insert smaller value
root = TreeNode(4)
root = Solution().insertIntoBST(root, 2)
assert inorder(root) == [2, 4]  # inserted into left subtree

# Test 3: Insert larger value
root = TreeNode(4)
root = Solution().insertIntoBST(root, 6)
assert inorder(root) == [4, 6]  # inserted into right subtree

# Test 4: Problem example 1
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

root = Solution().insertIntoBST(root, 5)
assert inorder(root) == [1, 2, 3, 4, 5, 7]  # standard insertion case

# Test 5: Deep insertion into skewed tree
root = TreeNode(1)
root.right = TreeNode(2)
root.right.right = TreeNode(3)

root = Solution().insertIntoBST(root, 4)
assert inorder(root) == [1, 2, 3, 4]  # insertion at deepest level

# Test 6: Negative values
root = TreeNode(0)
root = Solution().insertIntoBST(root, -5)
assert inorder(root) == [-5, 0]  # handles negative integers

# Test 7: Large values
root = TreeNode(100000000)
root = Solution().insertIntoBST(root, -100000000)
assert inorder(root) == [-100000000, 100000000]  # boundary constraints

# Test 8: Balanced tree insertion
root = TreeNode(8)
root.left = TreeNode(4)
root.right = TreeNode(12)

root = Solution().insertIntoBST(root, 10)
assert inorder(root) == [4, 8, 10, 12]  # insertion inside right subtree

Test	Why
Empty tree	Validates creation of the first node
Insert smaller value	Confirms left subtree insertion
Insert larger value	Confirms right subtree insertion
Problem example 1	Verifies standard BST insertion
Skewed tree	Tests worst-case traversal depth
Negative values	Ensures signed integers work correctly
Large values	Validates boundary constraints
Balanced tree insertion	Tests insertion into internal subtree

Edge Cases

Empty Tree

One important edge case occurs when the original BST is empty. In this scenario, root is None or nil.

A buggy implementation might assume the root always exists and attempt to access root.val, causing an error.

The solution handles this immediately with the base case:

if root is None:
    return TreeNode(val)

This correctly creates the first node in the tree.

Highly Skewed Tree

A BST can become completely unbalanced, behaving like a linked list.

For example:

Inserting another large value forces traversal through every node.

This case is important because it produces the worst-case time complexity of O(n).

The implementation still works correctly because it simply follows child pointers until a None child is found.

Insertion as Leftmost or Rightmost Node

The inserted value may become the smallest or largest value in the entire BST.

For example:

inserting 0 into a tree whose minimum is 1
inserting 100 into a tree whose maximum is 50

A flawed implementation could incorrectly stop traversal too early.

The recursive logic avoids this problem because comparisons continue until an empty child position is reached, regardless of how deep the insertion point becomes.