Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

BST Insert

BSTmedium

Implement `bstInsert(root, val)` returning a new BST with `val` inserted in the correct position, without mutating the input.

Sample tests

Input: bstInsert({"val":5,"left":null,"right":null}, 3)
Output: {"val":5,"left":{"val":3,"left":null,"right":null},"right":null}
Input: bstInsert(null, 7)
Output: {"val":7,"left":null,"right":null}

+ 1 hidden test run on Submit.

Hints

Common pitfalls
  • Mutating the existing nodes instead of returning new ones.

Learning resources

  • Wikipedia: Binary search tree
Approach & explanation (try first)

Recursing to the correct empty slot and rebuilding parents with spread inserts immutably in O(h).

Loading...
⌘/Ctrl + Enter

Run your code to see results.