{x}
blog image

Insert into a Binary Search Tree

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, 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 Explanation: Inserting into a Binary Search Tree

This problem involves inserting a new node with a given value (val) into a Binary Search Tree (BST). The key is to maintain the BST property: for every node, all nodes in its left subtree have smaller values, and all nodes in its right subtree have larger values.

Approach:

The most efficient way to solve this is using recursion. The algorithm works as follows:

  1. Base Case: If the current node (root) is null, it means we've reached the correct insertion point. We create a new node with the given val and return it.

  2. Recursive Step:

    • If root.val is greater than val, it means the new node should be inserted into the left subtree. We recursively call the insertIntoBST function on the left subtree (root.left). The result of this recursive call (the new root of the left subtree) is then assigned back to root.left.
    • If root.val is less than val, the new node should be inserted into the right subtree. We perform a similar recursive call on the right subtree (root.right) and update root.right.

  3. Return Value: The function always returns the (possibly updated) root of the subtree it's working on. This allows the changes to propagate up the tree.

Time Complexity: O(h), where h is the height of the BST. In the worst case (a skewed tree), h can be equal to n (the number of nodes), resulting in O(n) time complexity. However, in a balanced BST, h is log₂(n), leading to O(log n) time complexity.

Space Complexity: O(h) due to the recursive call stack. Again, in the worst case, this is O(n), and in a balanced tree, it's O(log n).

Code Examples:

The provided code demonstrates this recursive approach in several languages. All versions follow the same logic:

  • Python: Uses straightforward recursive calls and node definitions.

  • Java: Similar to Python, with standard Java TreeNode class definition.

  • C++: Uses pointers for the tree nodes.

  • Go: Employs Go's pointer-based approach to tree nodes.

  • TypeScript: Similar to the other languages, using TypeScript's type definitions.

Example Walkthrough (Python):

Let's trace the execution for the example root = [4,2,7,1,3], val = 5:

  1. insertIntoBST(root, 5) is called.
  2. root.val (4) is less than val (5), so we recursively call insertIntoBST(root.right, 5).
  3. root.right is 7. 7 > 5, so we recursively call insertIntoBST(root.right.left, 5).
  4. root.right.left is null. This is the base case! A new node with value 5 is created.
  5. The new node is returned up the call stack, eventually becoming the right child of node 2.

The final tree reflects the correct BST insertion of the node with value 5.