https://practice.geeksforgeeks.org/problems/binary-tree-to-dll/1 Hard 0 attempts
GeeksforGeeks ↗

https://practice.geeksforgeeks.org/problems/binary-tree-to-dll/1

Hard TreeBinary TreeDFS GeeksforGeeks

Take a binary tree and reshape it, in-place, into a doubly linked list. Reuse the existing node pointers rather than allocating new ones: each node's left pointer becomes the "previous" link of the list, and its right pointer becomes the "next" link. The order of nodes in the resulting list should match the tree's inorder sequence (left, node, right). Return the node that becomes the head of the list.

Input Format
Implement binaryTreeToDll(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement. The output is read along right pointers; left pointers must link backward correctly.

Sample Input and Output

Example 1 ยท Run Sample

Input
root = [10,12,15,25,30,36]
Output
[25,12,30,10,36,15]

Example 2

Input
root = [1]
Output
[1]
Constraints
  • 1 <= Number of nodes <= 10^5
  • -10^5 <= Node.val <= 10^5
Test Cases (2)
Case 1
Args: [[10,12,15,25,30,36]] Expected: [25,12,30,10,36,15]
Case 2
Args: [[1]] Expected: [1]
Topics
TreeBinary TreeDFS

Iterative Inorder with Previous Pointer

Visit nodes in inorder, saving each original right child before linking the current node to the preceding node. Reuse left and right as previous and next links.

javascript
function binaryTreeToDll(root) {
  const stack=[];let current=root,previous=null,head=null;
  while(current||stack.length) {
    while(current){stack.push(current);current=current.left;}
    const node=stack.pop(),right=node.right;
    node.left=previous;
    if(previous)previous.right=node;else head=node;
    previous=node;current=right;
  }
  if(previous)previous.right=null;
  return head;
}

Time: O(n) | Space: O(h) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript