Build a BST From a List
Updated
Problem statement
You are given an integer array values. Start with an empty binary search tree and insert the values one at a time, in the order they appear.
To insert a value x, start at the root. If x is smaller than the current node's value, move to its left child. Otherwise, when x is equal or larger, move to its right child. When the child you need is empty, put a new node with value x there. The first value becomes the root.
Return the root of the finished tree. The tree is shown in level order, with null for an empty child.
Function
buildBST(values: int[]) → TreeNodeExamples
Example 1
values = [5,3,8,1,4,9]return = [5,3,8,1,4,null,9]Insert 5 as the root. 3 is smaller than 5, so it becomes the left child. 8 is larger, so it becomes the right child. 1 goes left at 5 and left at 3. 4 goes left at 5 and right at 3. 9 goes right at 5 and right at 8.
In level order the tree is 5, then 3, 8, then 1, 4 under 3 and an empty left spot and 9 under 8, which is written [5,3,8,1,4,null,9].
Example 2
values = [7,7,2,7]return = [7,2,7,null,null,null,7]The first 7 is the root. The second 7 is equal to the root, so it goes right. 2 is smaller than 7, so it becomes the root's left child. The last 7 is equal to the root, so it goes right, then it is equal to the right child, so it goes right again.
Level order lists 7, then 2, 7, then the two empty children of 2, the empty left child of the second 7, and the last 7: [7,2,7,null,null,null,7].
Example 3
values = [1,2,3]return = [1,null,2,null,3]Each value is larger than every value before it, so each new node goes right at every step. The tree is a chain leaning right: [1,null,2,null,3].
Constraints
1 <= values.length <= 500-10^4 <= values[i] <= 10^4- Values may repeat.
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Gas Station Loop StartOA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
- Maximum Value of the Last RobotOA · Seen Aug 2021
Similar questions at other companies
- Preorder of a Special Binary TreeNielsen · OA
- Count Parent Nodes With a Target SumAdobe · OAAdobe interview questions
- Decision Tree Regression from ScratchNVIDIA · OANVIDIA interview questions
- Maximum Value in a Binary TreeAkuna Capital · PHONE SCREENAkuna Capital interview questions
- Balanced Binary TreeGoogle · PHONE SCREENGoogle interview questions
- Height-Balanced Binary TreeExpedia · ONSITE INTERVIEWExpedia interview questions
- Binary Tree Target-Sum PathsByteDance · PHONE SCREENByteDance interview questions
- Path Between Two Nodes of a Fibonacci TreeDatabricks · ONSITE INTERVIEWDatabricks interview questions
- Random Forest Classifier from ScratchMicrosoft · PHONE SCREENMicrosoft interview questions
- Construct a Binary Tree from Preorder and InordereBay · PHONE SCREENeBay interview questions