Flatten Binary Tree to Linked List
Hard Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Flatten a Binary Tree to a Linked List Following Preorder Traversal (In-Place), Binary Tree, Tree Traversal, Preorder Traversal, In-place Algorithm, Recursion, Stack, Iteration, Morris Traversal, Time Complexity, Space Complexity, Pointer, Linked List, Node, in-place algorithms, complexity analysis, morris traversal, stack, pointer operations, binary tree, preorder traversal, recursion, linked list, tree traversal, Iterative Tree Traversals.
Problem Statement Given the root of a binary tree, flatten it into a "linked list" in place. The "linked list" should be formed by using the right child pointer as the next pointer and setting the left child pointer to null. The nodes in the "linked list" should follow the same order as the pre order traversal of the original binary tree. Example 1: Explanation: The given binary tree has a preorder traversal order of [1, 2, 3, 4, 5, 6, 7]. To flatten the tree, it is converted into a linked list where the nodes follow the same order as the preorder traversal. The right pointer of each node in the linked list serves the function of the 'next' pointer, and the left pointer of each node is set to null. This process is done in place, meaning the existing binary tree structure is modified. Example 2: Explanation: The given binary tree has a preorder traversal order of [15, 40, 62, 10, 20]. To flatten the tree, it is converted into a linked list where the nodes follow the same order as the preorder traversal. The right pointer of each node in the linked list serves the function of the 'next' pointer, and the left pointer of each node is set to null. This process is done in place, meaning the existing binary tree structure is modified.