Insert a given node in BST

Intuition

The goal is to insert a new value into a Binary Search Tree (BST) while ensuring that the fundamental properties of the BST are preserved. A BST is organized in such a way that for any given node, all values in its left subtree are smaller than the node's value, and all values in the right subtree are larger. The insertion process requires identifying the correct location for the new value, ensuring that the tree remains correctly ordered. This involves traversing the tree, making comparisons at each node, and ultimately finding an appropriate null child position where the new node can be inserted, thereby maintaining the structure and properties of the BST.

Approach

Initiate a traversal of the tree to locate the correct insertion point by comparing the value to be inserted with the value of the current node.
If the value to be inserted is less than the value of the current node, proceed to explore the left subtree.
If the value to be inserted is greater than the value of the current node, proceed to explore the right subtree.
Continue this comparison and traversal process until a potential leaf position (a null child) is identified in the relevant subtree.
To insert the new value, create a new node containing the given value, and attach this new node as a child of the parent node at the empty position found in the previous step. If the value is less than the parent's node value, the new node should be attached as the left child; otherwise, it should be attached as the right child.
Return the updated Binary Search Tree, now including the newly inserted value while maintaining its properties.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
class TreeNode {
public:
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    // Recursive function to insert a value into the BST
    TreeNode* solve(TreeNode* node, int val) {
        // If the current node is NULL, create a new TreeNode with the given value
        if (node == nullptr) {
            return new TreeNode(val);
        }
        
        // Traverse the tree to find the correct insertion point
        if (val < node->data) {
            // Move to the left subtree
            node->left = solve(node->left, val);
        } else if (val > node->data) {
            // Move to the right subtree
            node->right = solve(node->right, val);
        }
        
        // Return the (potentially modified) node
        return node;
    }
public:
    // Public method to start the insertion process
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        return solve(root, val);
    }

    // Helper function to print the tree in-order
    void printInOrder(TreeNode* root) {
        if (root == nullptr) return;
        printInOrder(root->left);
        cout << root->data << " ";
        printInOrder(root->right);
    }
};

// Main function for testing
int main() {
    Solution solution;
    
    // Create a sample BST: [4, 2, 7, 1, 3]
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    
    int val = 5;
    // Insert the value into the BST
    TreeNode* newRoot = solution.insertIntoBST(root, val);
    
    // Print the BST in-order to verify the insertion
    solution.printInOrder(newRoot); // Output should be: 1 2 3 4 5 7
    cout << endl;

    // Clean up memory (optional, but recommended for large trees)
    // In practice, you would need a function to delete all nodes to avoid memory leaks

    return 0;
}
public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { data = val; left = null; right = null; }
}

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // If the root is null, create a new node with the given value and return it
        if (root == null) {
            return new TreeNode(val);
        }
        
        // Traverse the tree to find the correct insertion point
        TreeNode current = root;
        while (true) {
            if (val < current.data) {
                // Move to the left subtree
                if (current.left == null) {
                    current.left = new TreeNode(val);
                    break;
                } else {
                    current = current.left;
                }
            } else {
                // Move to the right subtree
                if (current.right == null) {
                    current.right = new TreeNode(val);
                    break;
                } else {
                    current = current.right;
                }
            }
        }
        
        // Return the modified tree's root node
        return root;
    }
    
    // Helper function to print the tree in-order
    private void printInOrder(TreeNode root) {
        if (root == null) return;
        printInOrder(root.left);
        System.out.print(root.data + " ");
        printInOrder(root.right);
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // Create a sample BST: [4, 2, 7, 1, 3]
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        
        int val = 5;
        root = solution.insertIntoBST(root, val);
        
        // Print the BST in-order to verify the insertion
        solution.printInOrder(root); // Output should be: 1 2 3 4 5 7
    }
}
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    # Recursive function to insert a value into the BST
    def solve(self, node, val):
        # If the current node is None, create a new TreeNode with the given value
        if node is None:
            return TreeNode(val)
        
        # Traverse the tree to find the correct insertion point
        if val < node.data:
            # Move to the left subtree
            node.left = self.solve(node.left, val)
        elif val > node.data:
            # Move to the right subtree
            node.right = self.solve(node.right, val)
        
        # Return the (potentially modified) node
        return node

    # Wrapper function to start the insertion process
    def insertIntoBST(self, root, val):
        return self.solve(root, val)

    # Helper function to print the tree in-order
    def printInOrder(self, root):
        if root is None:
            return
        self.printInOrder(root.left)
        print(root.data, end=' ')
        self.printInOrder(root.right)

# Main function for testing
def main():
    solution = Solution()
    
    # Create a sample BST: [4, 2, 7, 1, 3]
    root = TreeNode(4)
    root.left = TreeNode(2)
    root.right = TreeNode(7)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(3)
    
    val = 5
    # Insert the value into the BST
    new_root = solution.insertIntoBST(root, val)
    
    # Print the BST in-order to verify the insertion
    solution.printInOrder(new_root)  # Output should be: 1 2 3 4 5 7

# Run the main function
if __name__ == "__main__":
    main()
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *      constructor(val = 0, left = null, right = null){
 *          this.data = val;
 *          this.left = left;
 *          this.right = right;
 *      }
 * }
 **/

class Solution {
    // Recursive function to insert a value into the BST
    solve(node, val) {
        // If the current node is null, create a new TreeNode with the given value
        if (node === null) {
            return new TreeNode(val);
        }

        // Traverse the tree to find the correct insertion point
        if (val < node.data) {
            // Move to the left subtree
            node.left = this.solve(node.left, val);
        } else if (val > node.data) {
            // Move to the right subtree
            node.right = this.solve(node.right, val);
        }

        // Return the (potentially modified) node
        return node;
    }

    // Wrapper function to start the insertion process
    insertIntoBST(root, val) {
        return this.solve(root, val);
    }

    // Helper function to print the tree in-order
    printInOrder(root) {
        if (root === null) return;
        this.printInOrder(root.left);
        console.log(root.data);
        this.printInOrder(root.right);
    }
}

// Main function for testing
function main() {
    const solution = new Solution();
    
    // Create a sample BST: [4, 2, 7, 1, 3]
    const root = new TreeNode(4);
    root.left = new TreeNode(2);
    root.right = new TreeNode(7);
    root.left.left = new TreeNode(1);
    root.left.right = new TreeNode(3);
    
    const val = 5;
    // Insert the value into the BST
    const newRoot = solution.insertIntoBST(root, val);
    
    // Print the BST in-order to verify the insertion
    solution.printInOrder(newRoot); // Output should be: 1 2 3 4 5 7
}

// Run the main function
main();

Complexity Analysis

Time Complexity: O(H), where H is the height of the tree, which in the worst case can be N (for a skewed tree), but for a balanced BST, it will be log(N).

Space Complexity: O(1) Only a constant amount of space is used to store the current node and the new node, regardless of the size of the input tree.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code