# Flatten binary tree to linked list

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)?

• Not enough for a review, but note you shouldn't be returning anything ("Do not return anything, modify root in-place instead.", -> None:), yet you are (return root). Sep 30, 2019 at 16:57
• I wouldn't go so far as to say that it isn't working, but it's certainly not complete. Please show the source code for TreeNode. Sep 30, 2019 at 18:26
• Why is flatten in its own class called Solution? Is this a requirement for some online test? I'd think it makes more sense as a method on TreeNode if not a standalone function. Oct 1, 2019 at 3:11
• I've once tried it to, perhaps the answer could give you some insights: codereview.stackexchange.com/questions/226781/… Oct 1, 2019 at 6:27
• @bullseye The code works fine (especially now that the class was uncommented). Also, I believe you know you can't VTC if you don't have 3k rep Oct 1, 2019 at 13:15