Tech Blogs LLD SDE Playbook DSA

Insert into a Binary Search Tree

Medium Top 250
Associated Patterns
Trees
Interviewed At (Company Tags)
GoogleAmazonMicrosoft
External Reference View on LeetCode

Problem Description

You are given the root node of a binary search tree (BST) and a val 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 that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

Examples

Example 1:

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

Example 2:

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

Constraints

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

Recursive BST Traversal and Leaf Insertion

Because a BST maintains sorted order (left child smaller, right child larger), insertion is straightforward:

  • If the current node is null, we have found our insertion point. We create and return a new node new TreeNode(val).
  • If val is smaller than the current node’s value, we recurse on the left child: node.left = insertIntoBST(node.left, val).
  • If val is larger than the current node’s value, we recurse on the right child: node.right = insertIntoBST(node.right, val). Finally, return the modified node pointer.

Solution 1: Recursive Insertion

Search the tree down to the leaves, then append a new node at the matching empty slot.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }
}
# 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 not root:
            return TreeNode(val)
            
        if val < root.val:
            root.left = self.insertIntoBST(root.left, val)
        else:
            root.right = self.insertIntoBST(root.right, val)
            
        return root
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) {
            return new TreeNode(val);
        }

        if (val < root->val) {
            root->left = insertIntoBST(root->left, val);
        } else {
            root->right = insertIntoBST(root->right, val);
        }
        return root;
    }
};

Complexity Analysis

  • Time Complexity: O(h) where h is the tree height. In the best/average case (balanced BST), this is O(log n). In the worst case (skewed tree), this is O(n).
  • Space Complexity: O(h) auxiliary space due to the recursion call stack.

Solution 2: Iterative Insertion

Iterate pointers down the BST branches, keeping track of the parent node to link the new node.

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode curr = root;

        while (true) {
            if (val < curr.val) {
                if (curr.left == null) {
                    curr.left = new TreeNode(val);
                    break;
                }
                curr = curr.left;
            } else {
                if (curr.right == null) {
                    curr.right = new TreeNode(val);
                    break;
                }
                curr = curr.right;
            }
        }
        return root;
    }
}
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val)
            
        curr = root
        while True:
            if val < curr.val:
                if not curr.left:
                    curr.left = TreeNode(val)
                    break
                curr = curr.left
            else:
                if not curr.right:
                    curr.right = TreeNode(val)
                    break
                curr = curr.right
                
        return root
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) return new TreeNode(val);
        TreeNode* curr = root;

        while (true) {
            if (val < curr->val) {
                if (!curr->left) {
                    curr->left = new TreeNode(val);
                    break;
                }
                curr = curr->left;
            } else {
                if (!curr->right) {
                    curr->right = new TreeNode(val);
                    break;
                }
                curr = curr->right;
            }
        }
        return root;
    }
};

Complexity Analysis

  • Time Complexity: O(h) where h is the tree height.
  • Space Complexity: O(1) auxiliary space as we do not allocate stack frames during search.

← All Problems