algoadvance

Leetcode 701. Insert into a Binary Search Tree

Problem Statement

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. The function should return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

A binary search tree is a binary tree where for every node, the values in its left subtree are less, and the values in its right subtree are greater.

Clarifying Questions

1. Can the input tree be null?
   • Yes, the input tree can be null.
2. What kind of values will be in the BST and the insert value?
   • All values are integers.
3. Can the BST have duplicate values?
   • No, it is guaranteed that the new value does not exist in the original BST.
4. Are there any constraints on the size of the BST?
   • There are no explicit constraints, but typical constraints will likely keep the size within reasonable limits for performance considerations.

Strategy

1. Identify the insertion point:
   • Traverse the BST starting from the root.
   • If the value to be inserted is less than the current node’s value, move to the left child.
   • If the value to be inserted is greater than the current node’s value, move to the right child.
   • When an appropriate null position is found (either a current left or right child is null), create a new node and insert it there.
2. Handle the edge case:
   • If the tree is empty (i.e., root is null), create a new node with the given value and return it as the root.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

        TreeNode current = root;
        while (true) {
            if (val < current.val) {
                if (current.left == null) {
                    current.left = new TreeNode(val);
                    break;
                } else {
                    current = current.left;
                }
            } else {
                if (current.right == null) {
                    current.right = new TreeNode(val);
                    break;
                } else {
                    current = current.right;
                }
            }
        }
        return root;
    }
}

Time Complexity

• Average Case: O(log n)
  • In a balanced BST, the height of the tree is log(n), so on average, the insertion will require log(n) comparisons/movements.
• Worst Case: O(n)
  • In the worst case, the tree could be completely unbalanced (e.g., a linked list), in which the insertion operation might have to traverse all nodes.

Space Complexity

• O(1) for the iterative solution as no additional data structures are used. Only a few variables are needed to keep track of positions in the tree during traversal.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?