Medium · Trees

Convert Binary Tree to Doubly Linked List

Given the root of a binary tree, return the head of a new non-circular doubly linked list that holds the tree's values in in-order sequence (left subtree, node, right subtree). Each list node's Prev and Next point to its neighbours, both ends are nil, and an empty tree returns null.

Examples

Example 1

{
  "tree": [1, 3, 2, 4, 5]
}

Output: 4 ↔ 3 ↔ 5 ↔ 1 ↔ 2

Example 2

{
  "tree": [5, 3, 8, 2, 4, null, 9]
}

Output: 2 ↔ 3 ↔ 4 ↔ 5 ↔ 8 ↔ 9

Rebuild it in the studio

Core interview problems are free with a full runner and lessons; Pro opens the complete library.

More Trees problems