Insert into a Binary Search Tree

Med

#0655Time: O(H), where H is the height of the tree. In each step, we move one level down the tree. In the average case for a balanced BST, H is O(log N). In the worst case of a completely unbalanced (skewed) tree, H is O(N), where N is the number of nodes.Space: O(H), where H is the height of the tree. This space is used by the recursion call stack. In the average case for a balanced BST, H is approximately log(N), making the complexity O(log N). In the worst case of a skewed tree, H is N, leading to O(N) complexity.

Data structures

Tree Binary Tree Binary Search Tree

Prompt

You are given the root node of a binary search tree (BST) and a value 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.

Example 1:

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: 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 3:

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

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses recursion to traverse the binary search tree. It leverages the inherent recursive structure of a tree. The function calls itself on either the left or right subtree based on the comparison between the new value and the current node's value, until it finds an empty spot (a null child) to place the new node.

Algorithm

1. Define a recursive function insertIntoBST(node, val).
1. Base Case: If node is null, create a new TreeNode with val and return it. This is the position where the new node should be inserted.
1. Recursive Step:
- a. If val is less than node.val, the new node belongs in the left subtree. Recursively call insertIntoBST on the left child: node.left = insertIntoBST(node.left, val).
- b. If val is greater than node.val, the new node belongs in the right subtree. Recursively call insertIntoBST on the right child: node.right = insertIntoBST(node.right, val).
1. Return the node. The returned node is then linked back to its parent in the previous recursive call.

Walkthrough

The core idea is to define a function that takes a node and a value. If the node is null, it means we've found the insertion point. We create a new TreeNode with the given value and return it. If the value to be inserted is less than the current node's value, we recursively call the function on the left child. The result of this recursive call (the potentially modified left subtree) is then assigned back to the current node's left child pointer. If the value is greater, we do the same for the right child. Finally, the function returns the current node, which ensures the tree structure is correctly linked back up the recursion chain. The initial call would be insertIntoBST(root, val).

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode insertIntoBST(TreeNode root, int val) {18        if (root == null) {19            return new TreeNode(val);20        }21        22        if (val < root.val) {23            root.left = insertIntoBST(root.left, val);24        } else {25            root.right = insertIntoBST(root.right, val);26        }27        28        return root;29    }30}

Complexity

Time

O(H), where H is the height of the tree. In each step, we move one level down the tree. In the average case for a balanced BST, H is O(log N). In the worst case of a completely unbalanced (skewed) tree, H is O(N), where N is the number of nodes.

Space

O(H), where H is the height of the tree. This space is used by the recursion call stack. In the average case for a balanced BST, H is approximately log(N), making the complexity O(log N). In the worst case of a skewed tree, H is N, leading to O(N) complexity.

Trade-offs

Pros

The code is often more concise and elegant, closely mirroring the mathematical definition of a BST.
It's a very natural way to solve tree problems and can be easier to reason about.

Cons

The space complexity is proportional to the height of the tree due to the recursion stack.
It can lead to a stack overflow error for very deep or skewed trees.

This approach uses a loop to traverse the tree from the root down to find the correct insertion point. By using a pointer to keep track of the current node, it avoids recursion and the associated overhead of the call stack, making it more space-efficient.

Algorithm

1. Handle the edge case: If the root is null, create a new TreeNode with val and return it.
1. Initialize a pointer current to root.
1. Start a while loop that continues until the node is inserted.
1. Inside the loop, compare val with current.val:
- a. If val < current.val:
  - i. If current.left is null, this is the insertion point. Create a new TreeNode(val), set current.left to this new node, and break the loop.
  - ii. Otherwise, the search must continue in the left subtree. Update current to current.left.
- b. If val > current.val:
  - i. If current.right is null, this is the insertion point. Create a new TreeNode(val), set current.right to this new node, and break the loop.
  - ii. Otherwise, the search must continue in the right subtree. Update current to current.right.
1. After the loop terminates, return the original root.

Walkthrough

First, we handle the edge case of an empty tree. If the root is null, we create a new node and return it. If the tree is not empty, we use a pointer, let's call it current, initialized to the root. We then loop, traversing down the tree. Inside the loop, we compare the val with current.val. If val is smaller, we check the left child. If current.left is null, we've found the insertion point. We create the new node, attach it as current.left, and terminate the loop. Otherwise, we move current to its left child (current = current.left). A similar process is followed if val is larger, but for the right child. Since the problem guarantees the value is not already in the tree, this loop will always find a null link to attach the new node. Finally, we return the original root.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode insertIntoBST(TreeNode root, int val) {18        if (root == null) {19            return new TreeNode(val);20        }21        22        TreeNode current = root;23        while (true) {24            if (val < current.val) {25                if (current.left == null) {26                    current.left = new TreeNode(val);27                    break;28                }29                current = current.left;30            } else { // val > current.val31                if (current.right == null) {32                    current.right = new TreeNode(val);33                    break;34                }35                current = current.right;36            }37        }38        return root;39    }40}

Complexity

Time

O(H), where H is the height of the tree. The number of iterations in the loop is determined by the depth of the insertion point. On average, for a balanced tree, this is O(log N). In the worst case of a skewed tree, it is O(N).

Space

O(1). This approach uses a constant amount of extra space for the `current` pointer, regardless of the tree's size or shape.

Trade-offs

Pros

Optimal space complexity of O(1) as it only uses a few pointers.
Avoids the risk of stack overflow, making it robust for very deep or skewed trees.

Cons

The code can be slightly more verbose and less intuitive for those accustomed to recursive solutions for tree problems.

Solutions

Solution

1/** * 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 ( root . val < val ) { root . right = insertIntoBST ( root . right , val ); } else { root . left = insertIntoBST ( root . left , val ); } return root ; } }

1/** * 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 ( root -> val < val ) root -> right = insertIntoBST ( root -> right , val ); else root -> left = insertIntoBST ( root -> left , val ); return root ; } };

1# 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 : TreeNode , val : int ) -> TreeNode : def dfs ( root ): if root is None : return TreeNode ( val ) if root . val < val : root . right = dfs ( root . right ) else : root . left = dfs ( root . left ) return root return dfs ( root )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem