Flatten Tree to Linked List 🎯

Welcome to an exciting lesson on Flattening a Tree to a Linked List! This tutorial is designed for both beginners and intermediate learners. By the end of this lesson, you'll have a solid understanding of how to transform a tree structure into a linked list, a fundamental skill in data structures and algorithms.

Let's start with the basics. A tree is a data structure consisting of nodes where each node has zero or more children. In contrast, a linked list is a linear collection of data elements, each containing a reference (or link) to the next element in the sequence.

Why Flatten a Tree to a Linked List? 📝

Flattening a tree to a linked list is important because it allows us to traverse and manipulate the data more efficiently. It's a useful technique in various real-world scenarios, such as parsing XML files, implementing game trees, and many more.

The Challenge: Flattening a Binary Tree 💡

We'll focus on flattening a binary tree, where each node can have at most two children (left child and right child). Here's a simple example of a binary tree:

   1
  / \
 2   3

Our goal is to transform this binary tree into a linked list like this:

1 -> 2 -> 3

Let's Get Started 🚀

We'll create a recursive function to flatten the tree. In our function, we'll maintain a head pointer, which will keep track of the current node in the linked list.

Here's a simplified version of the function:

python

class Node:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None

def flatten(root):
    if not root:
        return None

    current = root
    stack = []
    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        current.left = None

        if current.right:
            current.right, temp = current.right, current
            stack.append(current.right)
            current.right = temp

        if stack:
            current = stack[-1]
            current.next = current.right
            current.right = None

💡 Pro Tip: In the above function, we first traverse the left child nodes and append them to a stack. Then, we pop a node from the stack and make it the head of the linked list. If there's a right child, we move it to the right of the current node, effectively creating a loop between the right child and the current node. After that, we point the next pointer of the current node to the right child (if it exists).

Putting it All Together ✅

Now let's create a binary tree and flatten it using our function:

python

root = Node(1)
root.left = Node(2)
root.right = Node(3)

root.left.left = Node(4)
root.left.right = Node(5)

flatten(root)

print_list = []
current = root
while current:
    print_list.append(current.val)
    current = current.next

print(print_list)  # Output: [1, 2, 4, 5, 3]

In this example, we created a binary tree with four nodes and flattened it using the flatten() function. The output is a linked list where each node is separated by a comma.

Quiz Time 🧮

By the end of this lesson, you should have a good grasp of flattening a binary tree to a linked list. Happy learning! 🎉