701. Insert into a Binary Search Tree LeetCode Solution

In this guide, you will get 701. Insert into a Binary Search Tree LeetCode Solution with the best time and space complexity. The solution to Insert into a Binary Search Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Insert into a Binary Search Tree solution in C++
4. Insert into a Binary Search Tree solution in Java
5. Insert into a Binary Search Tree solution in Python
6. Additional Resources

Problem Statement of 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.

Complexity Analysis

• Time Complexity: O(\log n) \to O(n)
• Space Complexity: O(\log n) \to O(n)

701. Insert into a Binary Search Tree LeetCode Solution in C++

class Solution {
 public:
  TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (root == nullptr)
      return new TreeNode(val);
    if (root->val > val)
      root->left = insertIntoBST(root->left, val);
    else
      root->right = insertIntoBST(root->right, val);
    return root;
  }
};
/* code provided by PROGIEZ */

701. Insert into a Binary Search Tree LeetCode Solution in Java

class Solution {
  public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null)
      return new TreeNode(val);
    if (root.val > val)
      root.left = insertIntoBST(root.left, val);
    else
      root.right = insertIntoBST(root.right, val);
    return root;
  }
}
// code provided by PROGIEZ

701. Insert into a Binary Search Tree LeetCode Solution in Python

class Solution:
  def insertIntoBST(self, root: TreeNode | None, val: int) -> TreeNode | None:
    if not root:
      return TreeNode(val)
    if root.val > val:
      root.left = self.insertIntoBST(root.left, val)
    else:
      root.right = self.insertIntoBST(root.right, val)
    return root
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.