Insert into a Binary Search Tree

MediumTreesbst

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the root of a binary search tree and an integer val that does not already appear in the tree. Insert val and return the root of the updated tree. Several different trees could hold the same values, so this problem pins one answer: insert val as a **new leaf** using the standard BST descent. Starting at the root, go left when val is smaller than the current node and right when it is larger, and attach the new node at the first empty spot you reach. Do not restructure or rebalance any existing nodes. If the tree is empty, the new node becomes the root. The result is graded by its level-order serialization.

Examples

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
5 > 4 goes right to 7; 5 < 7 goes left, which is empty, so 5 becomes the left child of 7.
Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]
25 descends 40 -> 20 -> 30 and becomes the left child of 30.
Input: root = [], val = 5
Output: [5]
An empty tree gets a single root.

Constraints

  • 0 <= number of nodes <= 10^4
  • -10^8 <= Node.val, val <= 10^8
  • All values in the tree are distinct
  • `val` does not already exist in the tree

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bst problems