701. Insert into a Binary Search Tree

Problem Description

In this problem, we are dealing with the operation of inserting a new node into a binary search tree (BST). A BST is a special kind of binary tree where the value of each node must be greater than all values stored in its left subtree and less than the values stored in its right subtree.

You are provided with two pieces of information:

The root node of the BST, which is the starting point from which we can traverse the entire tree.
A value that you need to insert into the BST.

The task is to insert the value into the BST by finding the correct position without violating the BST properties. After the insertion, the function must return the root node of the modified BST.

It is important to note that since the value does not already exist in the BST, there won't be any duplicate values after insertion. Additionally, there can be several valid insertion points that could maintain the BST properties. The function can return any valid final BST.

Intuition

The solution approach uses Depth-First Search (DFS), which is an algorithm for traversing or searching tree or graph data structures. The DFS approach is recursive, as it applies the same logic at each node starting from the root.

Here's how we arrive at the solution approach:

Begin at the root and compare the value with the root.val.
If the value is greater than root.val, the value must be inserted somewhere in the right subtree of the current node because of the BST property (all right subtree values should be greater). Thus, we perform DFS on the right child of the current node.
If the value is less than root.val, the value must be inserted in the left subtree. We then perform DFS on the left child of the current node.
If at any point, we find that the current node (root) is None, it means we have reached an external point in the BST where the new node can be attached. So, we create a new node with the value and return it.
As the recursion unwinds, each call updates its left or right child pointer to the newly created node if a new node was created below it.
When the top of the recursion stack is reached (the original root), the entire BST with the new value inserted is returned.

The recursive nature of this approach handles all possible cases for insertion and ensures the maintenance of the BST properties post-insertion.

Learn more about Tree, Binary Search Tree and Binary Tree patterns.

Solution Approach

The given problem is addressed by implementing a recursive function to perform a depth-first search (DFS) on the tree. Here is a step-by-step walk-through of dfs function implementation, considering the Reference Solution Approach provided:

The dfs function takes the current root node as its argument.
If the current root node is None, it implies that the value should be inserted at this point. Therefore, a new TreeNode with the insert val is returned.
If the current root node is not None, we compare the insert val with the current node's value (root.val) to decide the direction of traversal:
- If val is greater than root.val, we recursively call dfs on the right child of the current node and update root.right with the result of that call.
- If val is less than root.val, we recursively call dfs on the left child of the current node and update root.left with the result of that call.
Each recursive call to dfs follows the same logic until a position to insert the new value is found (when root is None).
Once the base case is reached and the new node is created, the recursion begins to unwind. Every recursive call returns the current state of the root node, either unchanged (if no insertion happened in the respective subtree) or updated (if the new node was appended to the subtree).
Eventually, the function unwinds to the first recursive call, which returns the modified root of the entire tree with the new value inserted while maintaining the BST properties.

Algorithms and data structures utilized in this approach:

Recursion: A function that calls itself, simplifying complex problems by breaking them down into self-similar sub-problems.
Binary Search Tree (BST): A binary tree with the property that for any given node, values in its left subtree are smaller, and values in its right subtree are larger.
DFS: A traversal algorithm that starts at the root node and explores as far as possible along each branch before backtracking.

The recursive implementation efficiently uses the natural structure of a BST to locate the proper insertion point, ensuring a valid BST at every step of the recursion.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Suppose we have the following binary search tree and we want to insert the value 4 into this tree:

        3
       / \
      1   5

And, here are the steps we would take following the solution approach:

Since the root value (3) is less than our value (4), we look to the right subtree of the root. The root has a right child with the value 5.
Now considering node with value 5 as the new root, we compare our value (4) to 5. Since 4 is less than 5, we need to explore the left subtree of this node.
The left child of node 5 is None, which means this is the position where we should insert our new value (4). So, we create a new node with value 4.
We then update the left child of node 5 to point to this new node.
As the recursion unwinds, we return to the original root, but now its right subtree includes our new value, resulting in the following BST:

Through this recursive DFS approach, we have inserted the value 4 into the BST while maintaining the BST properties. The resulting tree is a valid binary search tree with the new node correctly placed.

Solution Implementation

1class TreeNode:
2    def __init__(self, value=0, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7class Solution:
8    def insertIntoBST(self, root: TreeNode, value: int) -> TreeNode:
9        # Helper function to traverse the tree and insert the node
10        def insert_helper(node):
11            # If we've reached a null node, insert the new value here
12            if node is None:
13                return TreeNode(value)
14          
15            # Decide to proceed left or right depending on the value
16            if node.value < value:
17                # Value is greater, go to the right subtree
18                node.right = insert_helper(node.right)
19            else:
20                # Value is smaller or equal, go to the left subtree
21                node.left = insert_helper(node.left)
22
23            # Return the node with its updated children
24            return node
25
26        # Call helper function to start insertion from root
27        return insert_helper(root)
28

1// Class for the binary tree node structure
2class TreeNode {
3    int value;
4    TreeNode left;
5    TreeNode right;
6
7    // Constructor to create a node without children
8    TreeNode(int value) {
9        this.value = value;
10    }
11
12    // Constructor to create a node with specified left and right children
13    TreeNode(int value, TreeNode left, TreeNode right) {
14        this.value = value;
15        this.left = left;
16        this.right = right;
17    }
18}
19
20class Solution {
21  
22    // Inserts a value into a Binary Search Tree (BST) and returns the updated tree root.
23    public TreeNode insertIntoBST(TreeNode root, int value) {
24        // If the current node is null, we've found the position for the new value.
25        if (root == null) {
26            return new TreeNode(value);
27        }
28
29        // If the value is greater than the current node's value, insert into the right subtree.
30        if (root.value < value) {
31            root.right = insertIntoBST(root.right, value);
32        }
33        // If the value is less than or equal to the current node's value, insert into the left subtree.
34        else {
35            root.left = insertIntoBST(root.left, value);
36        }
37
38        // Return the node itself after performing the insertion to maintain tree connections.
39        return root;
40    }
41}
42

1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int value;
6    TreeNode *leftChild;
7    TreeNode *rightChild;
8  
9    // Constructor with no arguments initializes node with value 0 and null children.
10    TreeNode() : value(0), leftChild(nullptr), rightChild(nullptr) {}
11  
12    // Constructor with value argument sets the node value and initializes children to null.
13    TreeNode(int x) : value(x), leftChild(nullptr), rightChild(nullptr) {}
14  
15    // Constructor with value and children arguments initializes node with given values.
16    TreeNode(int x, TreeNode *left, TreeNode *right) : value(x), leftChild(left), rightChild(right) {}
17};
18
19class Solution {
20public:
21    /**
22     * Inserts a value into a binary search tree (BST) and returns the root node of the BST.
23     *
24     * @param root Pointer to the root node of the tree where value is to be inserted.
25     * @param val The value to be inserted into the BST.
26     * @return Returns the root of the BST after insertion of the value.
27     */
28    TreeNode* insertIntoBST(TreeNode* root, int val) {
29        // If root is null, the new value should be placed here, so create and return a new node.
30        if (!root) {
31            return new TreeNode(val);
32        }
33      
34        // If the value to insert is greater than the root's value, insert into the right subtree.
35        if (root->value < val) {
36            root->rightChild = insertIntoBST(root->rightChild, val);
37        }
38        // Otherwise, the value is less than or equal to the root's value, insert into the left subtree.
39        else {
40            root->leftChild = insertIntoBST(root->leftChild, val);
41        }
42      
43        // Return the unchanged root pointer.
44        return root;
45    }
46};
47

1// Node structure for the binary search tree.
2interface TreeNode {
3  value: number;
4  leftChild: TreeNode | null;
5  rightChild: TreeNode | null;
6}
7
8// Function to create a new tree node with a value, and with left and right children initialized to null.
9function createTreeNode(value: number, leftChild: TreeNode | null = null, rightChild: TreeNode | null = null): TreeNode {
10  return {
11    value: value,
12    leftChild: leftChild,
13    rightChild: rightChild
14  };
15}
16
17/**
18 * Inserts a value into a binary search tree (BST) and returns the root node of the BST.
19 *
20 * @param root - The root node of the tree where the value is to be inserted.
21 * @param value - The value to be inserted into the BST.
22 * @return The root of the BST after the insertion of the value.
23 */
24function insertIntoBST(root: TreeNode | null, value: number): TreeNode | null {
25  // If the root is null, create a new node with the value to be inserted and return it.
26  if (root === null) {
27    return createTreeNode(value);
28  }
29
30  // If the value to insert is greater than the root's value, recursively insert into the right subtree.
31  if (value > root.value) {
32    root.rightChild = insertIntoBST(root.rightChild, value);
33  } else { // If the value is less than or equal to the root's value, recursively insert into the left subtree.
34    root.leftChild = insertIntoBST(root.leftChild, value);
35  }
36
37  // Return the unchanged root node.
38  return root;
39}
40

Time and Space Complexity

Time Complexity

The time complexity of this code is O(H), where H is the height of the binary search tree (BST). This is because in the worst-case scenario, you may need to traverse from the root to the leaf node to find the correct spot for insertion, which takes a time proportional to the height of the tree.

Space Complexity

The space complexity is also O(H) because the code uses recursive calls to insert the new node. The maximum depth of the recursive call stack would also be the height of the tree in the worst-case scenario, which makes the space complexity proportional to the height of the tree. For a balanced BST, this would be O(log N), where N is the number of nodes in the BST. However, for a skewed BST (resembling a linked list), this would be O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don’t know