FastPrepConvert a BST to a Doubly Linked List

Convert a BST to a Doubly Linked List

Microsoft logoMicrosoft● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

Given a binary search tree root, convert its nodes into a linear doubly linked list in ascending key order.

Return a portable representation of the list: row i is [value, prevIndex, nextIndex], rows appear from head to tail, and -1 represents a missing neighbor. Return an empty matrix for an empty tree.

Function

bstToDoublyLinkedList(root: TreeNode) → int[][]

Examples

Example 1

root = [4,2,5,1,3]return = [[1,-1,1],[2,0,2],[3,1,3],[4,2,4],[5,3,-1]]

In-order traversal yields 1,2,3,4,5; the second and third columns encode each node's previous and next list indexes.

Example 2

root = []return = []

An empty tree produces an empty list representation.

Constraints

  • The tree contains at most 100000 nodes
  • -10^9 <= node.val <= 10^9
  • All node values are distinct
  • The input satisfies the binary-search-tree ordering property

More Microsoft problems

See Microsoft hiring insights
public int[][] bstToDoublyLinkedList(TreeNode root) {
  // Write your code here.
}
root[4,2,5,1,3]
expected[[1,-1,1],[2,0,2],[3,1,3],[4,2,4],[5,3,-1]]
Checking account…