Build an AVL Tree by Insertion
Updated
Problem statement
Starting with an empty AVL binary search tree, insert the values in keys in the given order and return the resulting root. After each insertion, restore the AVL rule: the heights of a node’s left and right subtrees differ by at most 1. Use height 0 for an empty subtree and height 1 for a leaf.
Follow standard insertion rotations: for a left-left imbalance rotate right; for left-right rotate the left child left and then the node right; apply the mirrored rules for right-right and right-left. These rules determine the required tree for the distinct keys.
The interview asks to insert 1 through 10 and allows a height helper; the candidate began coding before the interviewer ended that part. For this exercise, assume the generalized distinct-key array and finite bounds below. Return a native TreeNode; the workspace displays it in level order, using null for missing children and removing trailing nulls. Return an empty tree for an empty input.
Function
buildAVL(keys: int[]) → TreeNodeExamples
Example 1
keys = [1,2,3,4,5,6,7,8,9,10]return = [4,2,8,1,3,6,9,null,null,null,null,5,7,null,10]Insert the source sequence 1 through 10. Standard AVL rotations yield root 4, with subtrees rooted at 2 and 8. The output is the native level-order tree serialization.
Example 2
keys = [3,1,2]return = [2,1,3]Insertion of 2 creates a left-right imbalance at 3. Rotate its left child left, then rotate 3 right.
Constraints
- For this exercise, assume
0 <= keys.length <= 63. -1000 <= keys[i] <= 1000, and all keys are distinct.
More JP Morgan Chase Onsite Interview questions
- LFU CacheONSITE INTERVIEW · Seen Nov 2026
- LRU CacheONSITE INTERVIEW · Seen Nov 2026
- Employees Above Average SalaryONSITE INTERVIEW · Seen Sep 2026
- Highest-Earning Employees By DepartmentONSITE INTERVIEW · Seen Sep 2026
- K Largest Integers in Descending OrderONSITE INTERVIEW · Seen Aug 2026
- Tile a Three-Row Board with DominoesONSITE INTERVIEW · Seen Jan 2026
- Two SumONSITE INTERVIEW · Seen Nov 2025
- Intersection of Two ListsONSITE INTERVIEW · Seen Jan 2025
- Maximum Subarray SumONSITE INTERVIEW · Seen Jan 2025
- Fibonacci NumberONSITE INTERVIEW · Seen Nov 2024
Similar questions at other companies
- Path Between Two Nodes of a Fibonacci TreeDatabricks · ONSITE INTERVIEWDatabricks interview questions
- Build a Tree from Preorder and Inorder TraversalsStackAdapt · ONSITE INTERVIEWStackAdapt interview questions
- Simplify a Binary Expression TreeAmazon · ONSITE INTERVIEW
- Binary Tree Level Order TraversalGoogle · ONSITE INTERVIEWGoogle interview questions
- Sorted Doubly Linked List to Balanced BST In PlaceSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Lowest Common Ancestor Only When Both Targets ExistAdobe · ONSITE INTERVIEWAdobe interview questions
- Sum Root-to-Leaf NumbersMeta · ONSITE INTERVIEWMeta interview questions
- Validate Binary Search TreeGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Balanced Tree Node ReportNetflix · ONSITE INTERVIEWNetflix interview questions
- Verify Postorder Sequence of a BSTMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
Interview reports that mention this question
JP Morgan Chase interview experiences
- JPMorgan Quant Stats Superdays: 3 Experiences (Part 3 of 3)
- JPMorgan Quant Modeling Superdays: 7 Experiences (Part 2 of 3)
- JPMorgan Quant Intern Superday: 19 Experiences (Part 1 of 3)
- JP Morgan Chase Data and AI Intern Superday: 11 Experiences
- JPMorgan Code for Good India 2024: 6 Experiences (Part 5 of 5)