# 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). – Carcigenicate Sep 30 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. – Reinderien Sep 30 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. – Turksarama Oct 1 at 3:11
• I've once tried it to, perhaps the answer could give you some insights: codereview.stackexchange.com/questions/226781/… – dfhwze Oct 1 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 – IEatBagels Oct 1 at 13:15

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.
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.
• I'll just note, this is a Leetcode challenge, which necessitates the useless Solution class and the method signature requirements and the included docstring. I agree with your suggestions, but I think Leetcode set them off on the wrong foot here. leetcode.com/problems/flatten-binary-tree-to-linked-list – Carcigenicate Oct 1 at 17:09