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:

1. The root node of the BST, which is the starting point from which we can traverse the entire tree.
2. 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:

1. Begin at the root and compare the value with the root.val.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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:

1. The dfs function takes the current root node as its argument.
2. 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.
3. 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.
4. Each recursive call to dfs follows the same logic until a position to insert the new value is found (when root is None).
5. 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).
6. 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.

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:

1        3
2       / \
3      1   5

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

1. 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.

2. 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.

3. 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.

4. We then update the left child of node 5 to point to this new node.

5. As the recursion unwinds, we return to the original root, but now its right subtree includes our new value, resulting in the following BST:

1        3
2       / \
3      1   5
4         /
5        4

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

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.