Insert into a BST

Share

Given the root of a BST and a value to insert, insert the value into the BST and return the root. The new value does not exist in the original BST.

Example 1
Input: root=[4,2,7,1,3], val=5 → Output: [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]

Solution Approach

Recursively traverse the BST. Go left if val < root.val, right if val > root.val. When reaching a null node, create and return a new node.

  • If root == null: return new TreeNode(val).
  • If val < root.val: root.left = insert(root.left, val).
  • Else: root.right = insert(root.right, val).
  • Return root.
Java
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        if (val < root.val) root.left = insertIntoBST(root.left, val);
        else root.right = insertIntoBST(root.right, val);
        return root;
    }
}
  • Time Complexity: O(H)
  • Space Complexity: O(H)