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.

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 ; } }

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