FastPrep
Problem · Linked List

Sorted Doubly Linked List to Balanced BST In Place

Learn this problem
● MediumSalesforce logoSalesforceNEW GRADONSITE INTERVIEW
See Salesforce hiring insights

Problem statement

values[i] is the value of original doubly linked-list node i; nodes are linked in index order and values are nondecreasing. Reuse those nodes to form a height-balanced binary search tree, treating each node's previous pointer as its left child and next pointer as its right child. Do not create replacement tree nodes.

Return one row per original node, in index order, as [nodeIndex, leftIndex, rightIndex, parentIndex]; use -1 for a missing link. For every even-sized segment, choose its lower-middle node as the root, making the serialization deterministic.

Function

buildBalancedBstLinks(values: int[]) → int[][]

Examples

Example 1

values = [1,2,3,4]return = [[0,-1,-1,1],[1,0,2,-1],[2,-1,3,1],[3,-1,-1,2]]

Node 1 is the lower-middle root; every row identifies the reused original node and its final links.

Example 2

values = [-10,-3,0,5,9]return = [[0,-1,1,2],[1,-1,-1,0],[2,0,3,-1],[3,-1,4,2],[4,-1,-1,3]]

Node 2 is the root and both sides are recursively balanced.

Constraints

  • 1 <= values.length <= 200000
  • -1000000000 <= values[i] <= 1000000000
  • values is nondecreasing.
  • The returned link table is the required serialization; it does not represent newly allocated tree nodes.

More Salesforce problems

drafts saved locally
public int[][] buildBalancedBstLinks(int[] values) {
    // Write your code here
}
values[1,2,3,4]
expected[[0,-1,-1,1],[1,0,2,-1],[2,-1,3,1],[3,-1,-1,2]]
checking account