Leetcode: Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List | LeetCode OJ

We need to convert a binary tree to a linked list without creating more nodes. The pointers need to be modified such that the result represents a linked list

The trick to solve problem related to trees is to either use

1. divide and conquer technique and perform recursions on left and right subtrees or
2. use an appropriate traversal technique

In this case as per the given example we can perform a pre-order traversal using a stack.

1. Use a dummy node as the head of the resultant linked list, this should get connected to the first node of the pre-order traversal which is the root
2. Start with the root in the stack
3. Repeat until the stack is empty and perform the following operations
4. Pop the element on top and add it to the linked list
5. Now we need to ensure that the next node on top of the stack is the next node in the pre-order traversal
6. Find the left and right child of the popped node and we need left node on the top as it is the next node in the pre-order traversal
7. Hence we append right node to the stack first and then the left node
8. In this manner the next node to be popped is the left node which will get attached to the linked list and if it has another left child it will go on top thus maintaining the pre-order traversal.

Please work out this process using a pen and paper to get a hang of the algorithm

Remarks:

1. As we are iterating through all the nodes the time complexity is O(n)
2. Since we are using a stack to store node we can have a worst case space complexity of O(n)

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place 
        """
        if not root:
            return None
        a = TreeNode(0)
        st = [root]
        while st:
            p = st.pop()
            if p.right:
                st.append(p.right)
            if p.left:
                st.append(p.left)
            a.right = p
            p.left = None
            a = a.right