Flatten Binary Tree To Linked List - Leetcode Solution

Problem Statement: Given the root of a binary tree, flatten the tree into a "linked list": The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Solution: To solve this problem, we can do a preorder traversal of the binary tree and store all nodes in a list. Then, we can modify the binary tree to make it a linked list.

Algorithm:

1. Create a list to store the preorder traversal of the binary tree. (We can use recursion to do a preorder traversal of the binary tree)
2. Modify the binary tree to make it a linked list: ⦁ Set the root node as the first node in the list. ⦁ For each node in the list starting from the second node: ⦁ Set the left child of the previous node to null. ⦁ Set the right child of the previous node to the current node. ⦁ Set the left child of the last node in the list to null.

Pseudo-code: def flatten(root): # Step 1: Preorder traversal node_list = [] def preorder(node): if not node: return node_list.append(node) preorder(node.left) preorder(node.right) preorder(root)

# Step 2: Modify the binary tree
pre_node = None
for i in range(1, len(node_list)):
    pre_node = node_list[i-1]
    cur_node = node_list[i]
    pre_node.left = None
    pre_node.right = cur_node
pre_node.left = None

Time Complexity: O(n), where n is the number of nodes in the binary tree. We visit each node once during the preorder traversal.

Space Complexity: O(n), where n is the number of nodes in the binary tree. We need to store all nodes in the list during the preorder traversal.

1