Skip to content
CodeKruPro

Insert a value into a binary search tree

Coding problemEasy-MediumAsked in: Deloitte

A binary search tree keeps, for every node, all smaller values in its left subtree and all larger values in its right subtree. Given the root of such a tree and a value that is not in it yet, insert the value as a new leaf and return the root.

Walk down from the root: go left when the value is smaller than the node, right when it is larger, and attach the new node where the walk finds no child. Do not rebalance the tree (that means reorganising it to keep it short) or restructure it in any other way. If the tree is empty, the new node is the root.

Trees are written in level order, with null for a missing child.

Examples

Example 1
Input: root = [4,2,7,1,3], value = 5
Output: [4,2,7,1,3,5]
5 is larger than 4 and smaller than 7, so it becomes the left child of 7.
Example 2
Input: root = [], value = 5
Output: [5]
Example 3
Input: root = [5], value = 8
Output: [5,null,8]

Constraints

  • The tree has between 0 and 100,000 nodes with distinct values
  • All values, including value, are 32-bit integers
  • value is not in the tree

Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.

Run your code to see the results here.

This question is part of Pro+

Pro+ opens every question in Interview Prep and the mock interview. Every article and the first 2 questions of each topic stay free. Hands-on Selenium and API tasks follow their course lesson's own lock.

See Pro+

Already have Pro+? Sign in