algoadvance

You are given the root node of a Binary Search Tree (BST) and a value to insert into the tree. Insert the value into the BST in such a way that the resulting tree remains a valid BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Clarifying Questions

  1. Q: Are duplicates allowed in the BST? A: No, the problem guarantees that the new value does not exist in the original BST.

  2. Q: Can the input tree be empty? A: Yes, the tree can be empty, in which case the new value should become the root node.

  3. Q: Should we consider balancing the BST with this insertion? A: No, the problem does not require keeping the tree balanced, just that it remains a valid BST.

  4. Q: Is the tree guaranteed to be a valid BST before insertion? A: Yes, the tree given will be a valid BST.

Strategy

To insert a value into a BST:

  1. If the tree is empty, the new value will become the root node.
  2. Starting from the root, compare the new value with the current node value:
    • If the new value is smaller, move to the left subtree.
    • If the new value is greater, move to the right subtree.
  3. Insert the new value in the appropriate position when you find a null node.

Code

# Definition for a binary tree node.
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 root is None:
        return TreeNode(val)

    current = root
    while True:
        if val < current.val:
            if current.left is None:
                current.left = TreeNode(val)
                break
            else:
                current = current.left
        else:  # val > current.val because duplicates are not allowed
            if current.right is None:
                current.right = TreeNode(val)
                break
            else:
                current = current.right
                
    return root

Time Complexity

The time complexity of this solution is O(H), where H is the height of the BST. In the average case, the height of the BST is O(log N), where N is the number of nodes, but in the worst case (when the tree is skewed), the height can be O(N). Therefore, the time complexity ranges from O(log N) to O(N) depending on the structure of the tree.

Try our interview co-pilot at AlgoAdvance.com