Insert into a BST

Problem

Given the root of a BST and a value, insert the value into the tree (it is guaranteed not to already be present) and return the (possibly new) root.

Constraints

• 0 ≤ nodes ≤ 10⁴
• −10⁸ ≤ Node.val ≤ 10⁸

Approach — Tree Traversal

This is a Tree Traversal problem. The idea: traverse the tree — DFS recursively, or BFS level by level — and combine the results from each subtree. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def insertIntoBST(self, root, val):
        if not root:
            return TreeNode(val)
        cur = root
        while True:
            if val < cur.val:
                if not cur.left:
                    cur.left = TreeNode(val); return root
                cur = cur.left
            else:
                if not cur.right:
                    cur.right = TreeNode(val); return root
                cur = cur.right

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;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.