algoadvance

Leetcode 701. Insert into a Binary Search Tree

Problem Statement

You are given the root of a binary search tree (BST) and an integer value. You need to insert this value into the BST such that the BST property is maintained. Return the root of the modified BST. It is guaranteed that the new value does not exist in the original BST.

Example:

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

Clarifying Questions

1. Clarification on Value Insertion: Should the insertion maintain the BST property such that all nodes in the left subtree of a node are less than the node’s value and all nodes in the right subtree are greater?
   • Answer: Yes.
2. Return Type: Should we return the root of the new BST after insertion?
   • Answer: Yes.
3. Input Format: Are the input tree and the new value the only inputs provided?
   • Answer: Yes, the root of the BST and the integer value to insert are given as inputs.
4. Handling duplicates: How should we handle the scenario when the value to be inserted already exists in the BST?
   • Answer: The problem ensures that the new value does not exist in the BST.

Strategy

1. Recursively Traverse the Tree: Start at the root and recursively traverse the tree.
   • If the current node is null, we have found the correct spot for insertion, so return a new node with the given value.
   • If the current node’s value is greater than the value to insert, traverse the left subtree.
   • If the current node’s value is less than the value to insert, traverse the right subtree.
2. Updating Pointers: Once the correct spot is found, update the parent node’s left or right pointer accordingly.
3. Return the Modified Root: After the insertion, return the modified root of the BST.

Code

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        // Base case: we've reached the end of the tree or the tree is empty
        if (root == nullptr) {
            return new TreeNode(val);
        }
        
        // If the value to be inserted is less than the root's value, insert it into the left subtree.
        if (val < root->val) {
            root->left = insertIntoBST(root->left, val);
        }
        // If the value to be inserted is greater than the root's value, insert it into the right subtree.
        else {
            root->right = insertIntoBST(root->right, val);
        }
        
        // Return the root as it is (might have new left or right child now).
        return root;
    }
};

Time Complexity

• Insertion in a binary search tree has a time complexity of O(h), where h is the height of the tree.
• In the worst case, for an unbalanced BST (essentially resembling a linked list), the insertion time complexity would be O(n), where n is the number of nodes in the tree.
• For a balanced BST, the insertion time complexity would be O(log n).

Space Complexity

• The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

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?