LeetCode 701: Insert into a Binary Search Tree Solution

Master LeetCode problem 701 (Insert into a Binary Search Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

701. Insert into a Binary Search Tree

Medium

Tree Binary Search Tree Binary Tree

Problem Explanation

Explanation

To insert a value into a Binary Search Tree (BST), we need to maintain the properties of a BST. We can recursively traverse the tree to find the correct position to insert the new value. If the current node is null, we create a new node with the given value. Otherwise, we compare the value with the current node's value to decide whether to go left or right. We continue this process until we reach a null node and then insert the new node.

Algorithm:

Start from the root node.
If the root is null, create a new node with the given value and return it.
If the value is less than the root's value, recursively call the function on the left subtree.
If the value is greater than the root's value, recursively call the function on the right subtree.
Connect the new node to the correct position based on the comparisons.

Time Complexity:

The time complexity of this algorithm is O(log N) in the average case and O(N) in the worst case, where N is the number of nodes in the BST.

Space Complexity:

The space complexity of the algorithm is O(log N) in the average case due to the recursive calls on the stack. In the worst case, it can be O(N) if the tree is skewed.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 701 (Insert into a Binary Search Tree)?

This page provides optimized solutions for LeetCode problem 701 (Insert into a Binary Search Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 701 (Insert into a Binary Search Tree)?

The time complexity for LeetCode 701 (Insert into a Binary Search Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 701 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 701 in Java, C++, or Python.

Back to LeetCode Solutions