Insert into a Binary Search Tree

LeetCode 784 | Difficulty: Medium

Medium

Problem Description

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

Example 1:

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,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]

Constraints:

- The number of nodes in the tree will be in the range `[0, 10^4]`.

- `-10^8 <= Node.val <= 10^8`

- All the values `Node.val` are **unique**.

- `-10^8 <= val <= 10^8`

- It's **guaranteed** that `val` does not exist in the original BST.

Topics: Tree, Binary Search Tree, Binary Tree

---

Solutions

Solution 1: C# (Best: 120 ms)

Metric	Value
Runtime	120 ms
Memory	44.3 MB
Date	2022-01-13

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode InsertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);
        return InsertIntoBSTHelper(root, val);       
        
    }
    
    public TreeNode InsertIntoBSTHelper(TreeNode root, int val)
    {
        if(root==null) return new TreeNode(val);
        if(val<root.val)
        {
            root.left = InsertIntoBSTHelper(root.left, val);
        }
        else
        {
            root.right = InsertIntoBSTHelper(root.right, val);
        }
        return root;
    }    
}

📜 1 more C# submission(s)

Submission (2022-01-13) — 189 ms, 42.2 MB

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode InsertIntoBST(TreeNode root, int val) {
        TreeNode current = root;
        if(current == null) return new TreeNode(val);
        while(current != null)
        {
            if (val < current.val)
            {
                if(current.left == null) 
                {current.left = new TreeNode(val);
                 break;
                }
                else current = current.left;
                
            }
            else
            {
                if(current.right == null)
                {
                    current.right = new TreeNode(val);
                    break;
                }
                else current = current.right;
            }
        }
        
        return root;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.