grid47 Exploring patterns and algorithms
Oct 26, 2024
5 min read
Solution to LeetCode 114: Flatten Binary Tree to Linked List Problem
Given the root of a binary tree, flatten the tree into a ’linked list’ where each node’s right pointer points to the next node in pre-order traversal, and the left pointer of all nodes is null. The ’linked list’ should maintain the same order as a pre-order traversal of the binary tree.
Problem
Approach
Steps
Complexity
Input: The input consists of the root of a binary tree. The tree is represented as an array of node values, with null indicating missing nodes.
• The number of nodes in the tree is between 0 and 2000.
• Node values are between -100 and 100.
Output: The output should be the flattened tree represented as a linked list, where each node points to the next node in pre-order traversal, and the left pointer of each node is null.
Example: Output: [3,null,2,null,1,null,5,null,6]
Constraints:
• The right child pointer of each node should point to the next node in pre-order traversal.
• The left child pointer of each node should be null.
Goal: The goal is to flatten the binary tree such that it behaves like a linked list, while maintaining the pre-order traversal order.
Steps:
• Start from the root node and recursively flatten the left subtree.
• Rearrange the tree so that the right child points to the flattened left subtree.
• Set the left child of all nodes to null.
• Repeat the process for the right subtree.
Goal: The tree will have between 0 and 2000 nodes. The node values will range from -100 to 100.
Steps:
• The number of nodes is between 0 and 2000.
• Node values are in the range [-100, 100].
Assumptions:
• The tree is a valid binary tree.
• Input: Input: root = [3,2,5,1,null,null,6]
• Explanation: In pre-order traversal, the tree will be visited in this order: 3, 2, 1, 5, 6. The flattened tree should thus look like [3,null,2,null,1,null,5,null,6].
• Input: Input: root = []
• Explanation: If the input is an empty tree (root is null), the output should also be an empty list.
Approach: We can flatten the binary tree in-place using a depth-first traversal. At each node, we will adjust its right pointer to point to its left child (if any), and then recursively flatten the right subtree.
Observations:
• We can achieve this using a recursive depth-first search.
• The solution can be implemented without using extra space by flattening the tree in-place.
Steps:
• If the current node is null, return immediately.
• Store the right child of the current node in a temporary variable.
• Set the right child of the current node to its left child, and set the left child to null.
• Find the rightmost node of the current flattened tree and attach the temporary right subtree to it.
• Recursively flatten the right subtree.
Empty Inputs:
• If the input tree is empty (root is null), the output should be an empty list.
Large Inputs:
• The solution should efficiently handle large trees, up to 2000 nodes.
Special Values:
• Handle trees where the left and right subtrees are null, as well as trees where all nodes are on the left or right side.
Declare the function to flatten the binary tree into a linked list.
2 : Base Case
if( root ==NULL) return;
Handle the base case where the root is null.
3 : Temporary Storage
TreeNode* tmp = root->right;
Store the original right subtree temporarily.
4 : Pointer Update
root->right = root->left;
Assign the left subtree to the right pointer.
5 : Pointer Update
root->left =nullptr;
Set the left pointer to null.
6 : Node Traversal
TreeNode* node = root;
Initialize a pointer to traverse the right subtree.
7 : Node Traversal
while(node->right) node = node->right;
Traverse to the last node of the current right subtree.
8 : Pointer Update
node->right = tmp;
Reconnect the stored right subtree to the end of the current subtree.
9 : Recursive Call
flatten(root->right);
Recursively flatten the right subtree.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: In all cases, each node is visited once, so the time complexity is O(n), where n is the number of nodes in the tree.
Best Case: O(h)
Worst Case: O(h)
Description: The space complexity is O(h), where h is the height of the tree, due to the recursion stack. In the worst case (a skewed tree), h can be O(n).
