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

Given a binary tree, convert it to a doubly linked list (DLL) in-place. The left pointer of the tree node should act as the previous pointer of the DLL, and the right pointer should act as the next pointer. The DLL nodes should follow the inorder traversal order of the binary tree. Return the head of the DLL.

Example:

Input: tree = [10,12,15,25,30,36]
Output: 25 <-> 12 <-> 30 <-> 10 <-> 36 <-> 15
Sample Input
—
Sample Output
—
Constraints
  • 1 <= Number of nodes <= 10^5
  • -10^5 <= Node.val <= 10^5
Topics
TreeBinary TreeDFS

Approach: Inorder Traversal with Prev Pointer

Perform an inorder traversal. Maintain a prev pointer. For each visited node, set its left to prev and prev's right to the current node. The first node visited becomes the head.

function binaryTreeToDll(root) {
  let prev = null, head = null;
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    if (!prev) head = node;
    else { node.left = prev; prev.right = node; }
    prev = node;
    inorder(node.right);
  }
  inorder(root);
  return head;
}

Time Complexity: O(n)

Space Complexity: O(h) where h is tree height

Saved in this browser only. Private to you.

JavaScript