FastPrep
Problem · Tree

BST to Sorted Circular Doubly Linked List

Learn this problem
● MediumApple logoAppleFULLTIMEONSITE INTERVIEW

Problem statement

You are given the root of a binary search tree with distinct values. Convert that tree in place into a sorted circular doubly linked list:

  • Reuse each node's left pointer as previous.
  • Reuse each node's right pointer as next.
  • Link nodes in ascending order.
  • Join the smallest and largest nodes so the list is circular.

Do not allocate replacement list nodes. Return a serialization of the converted list beginning at its smallest node. Each output row is [value, previousValue, nextValue]. The source's null result for an empty tree is represented by an empty matrix. Storage for the returned rows is excluded from the in-place conversion requirement.

Function

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

Examples

Example 1

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

Inorder traversal is 1,2,3,4,5. The first node's previous pointer wraps to 5, and the last node's next pointer wraps to 1.

Example 2

root = []return = []

An empty tree produces an empty serialization.

Example 3

root = [7]return = [[7,7,7]]

In a one-node circle, both previous and next point back to the same node.

Constraints

  • The tree contains between 0 and 100000 nodes.
  • -1000000000 <= node.val <= 1000000000.
  • All node values are distinct.
  • The input satisfies the binary-search-tree ordering invariant.
  • The conversion must reuse the original tree nodes; recursion or an explicit traversal stack is allowed.
  • Output serialization storage is excluded from the in-place conversion requirement.

More Apple problems

drafts saved locally
public int[][] bstToCircularDoublyList(TreeNode root) {
    // Write your code here.
}
root[4,2,5,1,3]
expected[[1,5,2],[2,1,3],[3,2,4],[4,3,5],[5,4,1]]
checking account