Flatten binary tree to linked list

Question

I'm trying to flatten a binary tree into a linked list.

I have a working, correct solution:

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


def insert(root, node):
    if root.right is None:
        root.right = node 
        return None 
    else:
        insert(root.right, node)
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if root is None:
            return None 
        if root.left is None and root.right is None:
            return root 
        left = self.flatten(root.left)
        right = self.flatten(root.right)
        root.left = None
        if left:
            root.right = left 
            insert(root.right, right)
        else:
            root.right = right
        return root

I'm not certain, but I think the time complexity is \$O(n^2)\$. How do I make it run faster? Specifically, how do I modify it so that it runs in optimal time complexity (linear time)?

Answer 1

Encapsulating the wrong things

insert and flatten should be methods on TreeNode. Solution doesn't particularly need to exist as a class. Those two methods can assume that self is the root.

Return types

As @Carcigenicate suggested: what do you return from flatten? Probably the return type hint should be changed to TreeNode, and you should modify your comment to describe the circumstances under which None will or won't be returned.