706436. Flatten binary tree to linked list
Flatten Binary Tree to Linked List
Slug: flatten-binary-tree-to-linked-list
Difficulty: Medium
Topic Tags: Linked List, Tree, Data Structures
Company Tags: Microsoft
Summary
This problem requires you to take a binary tree and convert it into a linked list in such a way that the preorder traversal of the resulting linked list is identical to the inorder traversal of the original binary tree. The key concepts involved are tree traversal, linked lists, and recursion.
Detailed Explanation
The approach to this problem involves using a recursive function to traverse the binary tree in preorder (root-left-right), and while traversing, adding each node to the linked list as it's visited. This way, the nodes in the linked list will be in the same order as they were visited during the preorder traversal of the original binary tree.
Here is a step-by-step breakdown of the solution:
- Start by creating an empty linked list.
- Define a recursive function that takes the root node of the binary tree and the head of the linked list as parameters.
- If the current node is null, return the head of the linked list (since we've reached the end of the traversal).
- Add the current node to the linked list by creating a new node with the value from the current node and setting it as the next node in the linked list.
- Recursively call the function on the left child of the current node, passing the head of the linked list as the argument (to add any nodes on the left subtree).
- Finally, recursively call the function on the right child of the current node, again passing the head of the linked list as the argument.
- Return the head of the linked list.
The time complexity of this solution is O(n), where n is the number of nodes in the binary tree, since we visit each node once during the traversal. The space complexity is O(n) as well, due to the recursive call stack and the creation of new nodes in the linked list.
Optimized Solutions
Java
class Node {
int val;
Node left, right;
Node(int item) {
val = item;
left = right = null;
}
}
public class FlattenBinaryTreeToList {
public static void flatten(Node root) {
if (root == null)
return;
Node current = root;
while (current != null) {
if (current.left != null) {
// Find the rightmost node in the left subtree
Node rightmost = current.left;
while (rightmost.right != null)
rightmost = rightmost.right;
// Create a new node with the value from the rightmost node and set it as the right child of the current node
rightmost.right = current.right;
current.right = current.left;
current.left = null;
}
current = current.right;
}
}
}