Insert into a Binary Search Tree

Problem Statement

In this problem, you need to insert a given value into a Binary Search Tree (BST) that does not previously contain this value. After insertion, the tree must still satisfy BST properties:

• The left subtree of a node contains only nodes with values less than the node’s value.
• The right subtree only contains values greater than the node’s value.

The problem guarantees that the value to be inserted does not already exist in the tree. Any valid BST configuration after insertion is acceptable.

Examples

Example 1

Input:

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

Output:

[4,2,7,1,3,5]

Explanation:

One possible BST is:
    4
   / \
  2   7
 / \  /
1  3 5

Example 2

Input:

root = [40,20,60,10,30,50,70], val = 25

Output:

[40,20,60,10,30,50,70,null,null,25]

Explanation:

25 is inserted as the left child of 30:
    40
   /  \
 20    60
 / \   / \
10 30 50 70
    /
   25

Example 3

Input:

root = [4,2,7,1,3,null,null,null,null,null,null], val = 5

Output:

[4,2,7,1,3,5]

Explanation:

5 is added as the left child of 7.

Constraints

• The number of nodes in the tree is in the range [0, 10^4].
• -10^8 <= Node.val <= 10^8
• All Node.val values are unique.
• -10^8 <= val <= 10^8
• val does not exist in the original BST.

Approach and Intuition

To insert a value into a BST and preserve its structure:

1. Base Case:

   • If the root is None, return a new node with the value. This becomes the root.

2. Recursive Traversal:

   • Start from the root and compare the value to insert:

     • If val < root.val, recurse into the left subtree.
     • If val > root.val, recurse into the right subtree.

   • Once a None position is found in the correct direction, insert the new node there.

3. Return the Root:

   • After insertion, return the (possibly unchanged) root node.

This strategy ensures BST integrity and works in O(h) time, where h is the height of the tree. Since multiple valid configurations are acceptable, there’s no need to balance or reshape the tree.

This method handles all edge cases, including inserting into an empty tree or adding to any depth level of the existing tree.

Solutions

class Solution {
  public TreeNode addValueToBST(TreeNode root, int value) {
    TreeNode current = root;
    while (current != null) {
      if (value > current.val) {
        if (current.right == null) {
          current.right = new TreeNode(value);
          return root;
        }
        else current = current.right;
      }
      else {
        if (current.left == null) {
          current.left = new TreeNode(value);
          return root;
        }
        else current = current.left;
      }
    }
    return new TreeNode(value);
  }
}