Leetcode 114. Flatten Binary Tree to Linked List

Problem Explanation:

The problem at hand requires to flatten a binary tree to a linked list. The transformation should be done in place, i.e., you should not create a new tree or node but just re-use the existing nodes.

Let's walk through an example for better understanding.

1
2
3Given binary tree:
4
5    1
6   / \
7  2   5
8 / \   \
93   4   6

After flattening:

1
2
31
4 \
5  2
6   \
7    3
8     \
9      4
10       \
11        5
12         \
13          6

Here, in the flattened tree on the right side, you can see that the tree has been converted into a singly linked list where 1-->2-->3-->4-->5-->6.

Approach:

The solution for this problem is done by using Depth-First-Search (DFS).

Firstly, we flatten the left and right subtrees. Then, we set 'left' of the root to null and 'right' of the root to the flattened left subtree. After that, we proceed to attach the flattened right subtree to the end of the new right subtree, which started as the left subtree of the root.

For the given problem, DFS traverses nodes in the order of 1-2-3-4-5-6 which gives us the correct order for the flattened tree.

JavaScript Solution:

1
2javascript
3var flatten = function(root) {
4    if (root == null) return;
5    
6    flatten(root.right);
7    flatten(root.left);
8
9    root.right = prev;
10    root.left = null;
11    prev = root;
12};

Python Solution:

1
2python
3class Solution:
4    def __init__(self):
5        self.prev = None
6        
7    def flatten(self, root):
8        if not root:
9            return None
10        self.flatten(root.right)
11        self.flatten(root.left)
12        
13        root.right = self.prev
14        root.left = None
15        self.prev = root

Java Solution:

1
2java
3class Solution {
4    private TreeNode prev = null;
5
6    public void flatten(TreeNode root) {
7        if (root == null)
8            return;
9        flatten(root.right);
10        flatten(root.left);
11        root.right = prev;
12        root.left = null;
13        prev = root;
14    }
15}

C++ Solution:

1
2cpp
3class Solution {
4 private:
5  TreeNode* prev = nullptr;
6
7 public:
8  void flatten(TreeNode* root) {
9    if (root == nullptr)
10      return;
11    flatten(root->right);
12    flatten(root->left);
13    root->right = prev;
14    root->left = nullptr;
15    prev = root;
16  }
17};

C# Solution:

1
2csharp
3public class Solution {
4    private TreeNode prev = null;
5
6    public void Flatten(TreeNode root) {
7        if (root == null)
8            return;
9        Flatten(root.right);
10        Flatten(root.left);
11
12        root.right = prev;
13        root.left = null;
14        prev = root;
15    }
16}

In all the above solutions, the depth-first-search is applied sequentially from the rightmost node, moving towards the left. The prev node is used to keep track of the previously traversed node so that the tree can be re-shaped correctly while traversing. It involves recursively flattening the right subtree before the left subtree. Then, re-arrange pointers with the help of 'prev' node.Every time a node is processed, the 'left' pointer of the node is set to null, and the 'right' pointer is set to point to the previously flattened subtree.

The time complexity for this approach is O(n), where n is the number of nodes in the binary tree. This is because each node is visited exactly once during the depth-first traversal.

The space complexity is O(h), where h is the height of the binary tree. This is required for the call stack during the recursive traversals.

Notice that the height of a binary tree of 'n' nodes is approximately log(n). Therefore, the space complexity is usually not problematic.

Thus, the binary tree can be effectively flattened into a linked list by applying depth-first-search, and re-arranging the pointers efficiently. This approach is applicable to binary trees of any shape and size, and is quite efficient in terms of time and space complexity.

Importantly, this solution is implemented in place, meaning existing node structures are used without creating new ones.

Conclusion

Flattening a binary tree to a linked list is a problem that puts your understanding of the concepts of binary trees, linked lists, and depth-first search into practice. It is an interesting problem that involves re-arranging pointers while performing tree traversals.

Happy Coding, and keep practicing data structures and algorithms. Whether you choose Python, JavaScript, Java, or any other language, the fundamental concepts remain the same and you'll keep becoming a better problem solver with each problem you solve.