Flatten Binary Tree to Linked List

Flatten a binary tree to a fake “linked list” in pre-order traversal.

Question

Flatten a binary tree to a fake “linked list” in pre-order traversal.

Here we use the right pointer in TreeNode as the next pointer in ListNode.

Example:

Input:{1,2,5,3,4,#,6}
Output：{1,#,2,#,3,#,4,#,5,#,6}
Explanation：
     1
    / \
   2   5
  / \   \
 3   4   6

1
\
 2
  \
   3
    \
     4
      \
       5
        \
         6


Input:{1}
Output:{1}
Explanation：
         1
         1

Analyzation

Recursion

This problem can be divided into two parts: left subtree and right subtree.

Firstly, flatten the left subtree and right subtree using recursion.

Secondly, save the right subtree into temp and connect the left subtree to the root and put left subtree to None.

Thirdly, go to the very right node of the tree (this is the flattened left subtree) and connect the original flattened right subtree and we are done.

The Code

class Solution:
    """
    @param root: a TreeNode, the root of the binary tree
    @return: nothing
    """
    def flatten(self, root):
        # write your code here
        self.flatten_and_return_last_node(root)
        
    # restructure and return last node in preorder
    def flatten_and_return_last_node(self, root):
        if root is None:
            return None
            
        # flatten the left subtree
        self.flatten_and_return_last_node(root.left)
        # flatten the right subtree
        self.flatten_and_return_last_node(root.right)
        # save the right subtree as temp
        temp = root.right
        # make the right subtree as left subtree
        root.right = root.left
        # make the left subtree as None
        root.left = None
        # go to the very right node (the flattened left subtree)
        while (root.right):
            root = root.right
        # connect the original right subtree to the new tree
        root.right = temp
        
        return root.right

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).