700144. Binary Tree to DLL
Hard
Here is the detailed Markdown blog post for the GeeksforGeeks problem "Binary Tree to DLL":
# Binary Tree to DLL
Slug: binary-tree-to-dll
Difficulty: Hard
Id: 700144
Topic Tags: Linked List, Tree, Data Structures
Company Tags: Morgan Stanley, Accolite, Amazon, Microsoft, Snapdeal, Goldman Sachs, Salesforce
## Summary
The problem is about converting a given binary tree into a doubly-linked list. The key concepts involved are binary trees and linked lists.
## Detailed Explanation
To solve this problem, we will first perform an in-order traversal of the binary tree to get all the nodes in ascending order. Then, we will create a new linked list and add each node from the tree to the list while linking them correctly.
Here's a step-by-step breakdown of the solution:
1. Perform an in-order traversal of the binary tree to get all the nodes in ascending order.
2. Create a new doubly-linked list (DLL) with a head node.
3. Iterate through the nodes obtained from the in-order traversal and add each node to the DLL as follows:
- For the first node, set its `prev` pointer to `NULL` and its `next` pointer to the head of the DLL.
- For subsequent nodes, set their `prev` pointer to the previous node's `next` pointer (i.e., the current node becomes the new last node in the list) and their `next` pointer to the next node (if it exists).
4. Return the head of the DLL as the resulting doubly-linked list.
Here is an ASCII art diagram illustrating the conversion:
1
/ \
2 3
/ \
4 5 6
becomes:
-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <->
Time complexity: O(n), where n is the number of nodes in the binary tree.
Space complexity: O(1), as we only use a constant amount of space to store the DLL's head and the current node being processed.
## Optimized Solutions
### Java
class Node {
int val;
Node left, right;
public Node(int v) {
val = v;
left = right = null;
}
}
public class BinaryTreeToDLL {
public static Node convert(Node root) {
if (root == null) return null;
Node head = null;
Node prev = null;
Stack<Node> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (prev != null) {
root.right = prev;
prev.left = root;
} else {
head = root;
}
prev = root;
root = root.right;
}
return head;
}
}