We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Insert into a Binary Search Tree

Difficulty: Medium

Problem Description

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.

Key Insights

  • A binary search tree (BST) maintains the property that for any node, values in the left subtree are less than the node's value, and values in the right subtree are greater.
  • To insert a new value, traverse the tree starting from the root, moving left or right depending on whether the value is less than or greater than the current node's value.
  • The insertion process stops when a null position is found, where the new node can be added.

Space and Time Complexity

Time Complexity: O(h), where h is the height of the tree. In the worst case, h can be O(n) for a skewed tree and O(log n) for a balanced tree. Space Complexity: O(1) for iterative approach, O(h) for recursive approach due to the call stack.

Solution

The solution involves traversing the binary search tree starting from the root node. Depending on the value to be inserted, we will move left if the value is less than the current node's value, and right if it is greater. This traversal continues until we reach a leaf position (null) where we can insert the new node. The tree's structure as a binary search tree guarantees that this method will maintain the BST properties after insertion.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insertIntoBST(root: TreeNode, val: int) -> TreeNode:
    if not root:
        return TreeNode(val)  # If the root is None, create a new node with the value
    if val < root.val:
        root.left = insertIntoBST(root.left, val)  # Recur to the left subtree
    else:
        root.right = insertIntoBST(root.right, val)  # Recur to the right subtree
    return root  # Return the unchanged node pointer
← Back to All Questions