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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Insert into a Binary Search Tree

Number: 784

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Microsoft

Problem Description

Given the root of a Binary Search Tree (BST) and a value to insert, insert the new value into the tree while maintaining the BST properties. It is guaranteed that the value does not already exist in the tree. Return the root of the modified tree. Multiple valid BST structures may result from the insertion.

Key Insights

  • A BST has the property that for any node, all the nodes in its left subtree are smaller and all the nodes in its right subtree are larger.
  • Insertion into a BST involves following the BST property and finding the appropriate null location to attach the new node.
  • The process can be implemented recursively or iteratively.
  • The problem guarantees uniqueness so no duplicate checks are needed.

Space and Time Complexity

Time Complexity: O(h) where h is the height of the BST (in the worst case, for a skewed tree, O(n)). Space Complexity: O(h) for the recursion stack in the recursive approach (or O(1) with an iterative solution).

Solution

We use the BST property to insert the new node. Starting from the root, if the value to insert is less than the current node's value, we proceed to the left subtree; otherwise, we proceed to the right subtree. This continues until we find a null pointer where we can insert the new value as a new node. Key steps:

  • Check if the current node is null; if yes, create a new node with the given value.
  • Recurse (or iterate) down the tree until the correct insertion point is found.
  • Update the left or right pointers accordingly. This approach uses recursion for clarity, though an iterative implementation is also straightforward.

Code Solutions

# Define the structure for a tree node
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def insertIntoBST(root, val):
    # If reaching a null node, insert the new node here.
    if root is None:
        return TreeNode(val)
    # If the value to insert is less than the current node's value,
    # move to the left subtree.
    if val < root.val:
        root.left = insertIntoBST(root.left, val)
    # Otherwise, move to the right subtree.
    else:
        root.right = insertIntoBST(root.right, val)
    # Return the unchanged root pointer.
    return root

# Example usage:
# root = TreeNode(4)
# root.left = TreeNode(2)
# root.right = TreeNode(7)
# root.left.left = TreeNode(1)
# root.left.right = TreeNode(3)
# new_root = insertIntoBST(root, 5)
← Back to All Questions