Insert Into A Binary Search Tree Leetcode Problem 701 [Python Solution]

In this blog post, we'll delve into the Insert Into A Binary Search Tree problem, categorized under Trees and found on LeetCode.

This problem is rated as medium difficulty and is often encountered in technical interviews, particularly by tech giants like Google.

Problem Overview

Question: You are given the root node of a binary search tree (BST) and a value to insert into the tree.

Your task is to return the root node of the BST after the insertion.

The guarantee here is that the new value does not already exist in the original BST.

It's worth noting that there can be multiple valid ways to perform the insertion, as long as the tree maintains its BST property.

In other words, you can return any valid solution.

Let's understand the problem with an example.

Example 1:

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

Here's the tree after inserting 5:

Constraints:

The number of nodes in the tree will be in the range [0, 10^4].
Node values are unique, ranging from -10^8 to 10^8.
The value to insert, val, is guaranteed not to exist in the original BST.

Understanding BST Constraints

Before we dive into the solution, it's crucial to understand the constraints of a Binary Search Tree (BST).

In a BST:

For every node, all nodes in its left subtree have values less than the node's value.
For every node, all nodes in its right subtree have values greater than the node's value.

This property applies recursively to all nodes within the tree.

Now, let's explore the solution.

Insert into a Binary Search Tree LeetCode Problem Solution

We'll provide a Python solution to this problem.

The goal is to insert a value val into the BST while maintaining its integrity as a Binary Search Tree.

1. Bruteforce Approach

A brute-force approach to solve this problem involves recursively traversing the tree to find the appropriate location to insert the new value.

Here's the Python code for this approach:

def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
    # Base case: If the tree is empty, create a new node with the given value.

if not root:
        return TreeNode(val)
    
    # Recursively search for the insertion point.

if val < root.val:
        root.left = self.insertIntoBST(root.left, val)
    else:
        root.right = self.insertIntoBST(root.right, val)
    
    return root

This code starts by checking if the tree is empty (root is None).

If it is, it creates a new node with the value val and returns it.

Otherwise, it recursively traverses the tree by comparing the value val with the current node's value (root.val).

If val is less than the current node's value, it moves to the left subtree; otherwise, it moves to the right subtree.

The function keeps doing this until it finds an empty spot to insert the new node.

2. Efficient Approach

The brute-force approach works, but it might not be the most efficient solution, especially for large trees.

There's a more efficient way to insert a node while avoiding unnecessary recursive calls.

In this approach, we'll iterate through the tree using a while loop, and we'll track the current node (cur).

We'll keep updating cur based on the comparison between val and the values of nodes.

When we reach a null position, we'll insert the new node at that point.

Let's write Python code for this approach:

View on GitHub ➹

def insertIntoBST(self, root: TreeNode, val: int) -&gt; TreeNode:
    # Base case: If the tree is empty, create a new node with the given value.

if not root:
        return TreeNode(val)

    # Use a pointer to keep track of the current node.

cur = root

    while True:
        if val &lt; cur.val:
            if not cur.left:
                cur.left = TreeNode(val)
                break
            else:
                cur = cur.left
        else:
            if not cur.right:
                cur.right = TreeNode(val)
                break
            else:
                cur = cur.right

    return root

This code also starts by checking if the tree is empty.

If it is, it creates a new node with the value val and returns it.

If the tree is not empty, it initializes a pointer cur to the root and enters a while loop.

Inside the loop, it compares val with the current node's value (cur.val).

If val is less than the current value, it moves to the left subtree.

If the left child is empty, it inserts the new node and breaks out of the loop.

If the left child is not empty, it updates cur to the left child and continues the loop.

The same logic applies when val is greater than or equal to the current node's value, but it moves to the right subtree in that case.

This approach efficiently inserts the new node without unnecessary recursive calls.

Time and Space Complexity

Let's analyze the time and space complexity of our efficient approach:

Time Complexity: In the worst case, the time complexity is O(H), where H is the height of the tree.

This is because we traverse the tree from the root to the insertion point, and the height of the tree determines the number of steps required.

Space Complexity: The space complexity is O(1) as we use a constant amount of extra memory for the cur pointer and temporary variables.

There's no additional space used for function call stacks, making it a memory-efficient solution.

Reasoning Behind Our Approach

Our approach effectively leverages the binary search tree's properties to insert a new node in an efficient manner.

By iteratively navigating the tree using a while loop, we avoid the overhead of recursive function calls.

This makes the code more memory-efficient and well-suited for larger trees.

We handle the edge case of an empty tree by creating a new node as the root if necessary.

For non-empty trees, we use a pointer to traverse the tree while comparing values and identifying the appropriate insertion point.

Conclusion

In this blog post, we've explored the Insert Into A Binary Search Tree problem on LeetCode.

We've provided both a brute-force and an efficient approach to solve this problem, with a focus on the efficient approach.

The key to solving this problem efficiently lies in understanding the Binary Search Tree's properties and leveraging them to insert a new node in a way that maintains the tree's integrity.

If you found this guide helpful, please feel free to comment, ask questions, make suggestions, and share the content.

We encourage your engagement and are here to assist you in your coding journey.

For further practice and resources, you can visit neatcode.io, which offers a wide range of free

resources to help you prepare for coding interviews.

Thank you for reading, and we hope to see you again soon.

Link to the problem on LeetCode.

Happy coding!

Insert Into A Binary Search Tree Leetcode Problem 701 [Python Solution]

Problem Overview

Example 1:

Constraints:

Understanding BST Constraints

Insert into a Binary Search Tree LeetCode Problem Solution

1. Bruteforce Approach

2. Efficient Approach

Time and Space Complexity

Reasoning Behind Our Approach

Related Interview Questions By Company:

Related Interview Questions By Difficulty:

Related Interview Questions By Category:

Conclusion

Written By

CID

Tags