Flatten Binary Tree to Linked List

Data Structures and Algorithms

Statement

Given the root of a binary tree, flatten the tree into a linked list. The left child pointer of each node in the linked list should always be null, and the right child pointer should point to the next node in the linked list. The nodes in the linked list should be in the same order as that of preorder traversal of the given binary tree.

Constraints

• -100 ≤ node.data ≤ 100
• 1 ≤ number of nodes ≤ 500

Solution

"""
production algorithm
"""


class Solution:
    def flatten_tree(self, root):
        """
        time complexity O(n)
        space complexity O(1)
        """
        current = root
        while current:
            if current.left:
                last = current.left
                while last.right:
                    last = last.right
                last.right = current.right
                current.right = current.left
                current.left = None
            current = current.right
        return root

"""
unit tests
"""

from unittest import TestCase
from algorithms.dfs.flatten_binary_tree_to_linked_list.solution import Solution
from data_structures.binary_tree.binary_tree import BinaryTreeNode


class SolutionTestCase(TestCase):
    def test_flatten_tree(self):
        # Given
        root = BinaryTreeNode(1)
        root.left = BinaryTreeNode(2)
        root.right = BinaryTreeNode(3)
        root.left.left = BinaryTreeNode(4)
        root.left.right = BinaryTreeNode(5)
        root.right.left = BinaryTreeNode(6)
        root.right.right = BinaryTreeNode(7)
        root.left.left.left = BinaryTreeNode(8)
        root.left.left.right = BinaryTreeNode(9)
        root.left.right.left = BinaryTreeNode(10)
        root.left.right.right = BinaryTreeNode(11)
        root.right.left.left = BinaryTreeNode(12)
        root.right.left.right = BinaryTreeNode(13)
        root.right.right.left = BinaryTreeNode(14)
        root.right.right.right = BinaryTreeNode(15)
        solution = Solution()

        # When
        result = solution.flatten_tree(root)

        # Then
        current = result
        for n in [1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15]:
            self.assertEqual(current.data, n)
            self.assertEqual(current.left, None)
            current = current.right

Strategy

Depth First Search.

Explanation

The algorithm iterates all nodes. For each iteration, the algorithm finds the last node of preorder traversal in the left subtree, call it l, and the first node of preorder traversal in the right subtree, call it r. Then, the algorithm points l.right to r, shifts the left subtree to the right subtree, sets the left subtree to null, and then steps to the right.

Time Complexity

The algorithm operates on every node once. Therefore, the time complexity of the algorithm is O(n).

Space Complexity

The auxiliary space complexity of the algorithm is O(1).

Links

data_structures_algorithms/algorithms/dfs/flatten_binary_tree_to_linked_list at main ·…