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

• Carcigenicate: 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).
• Reinderien: 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.
• Turksarama: 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.
• dfhwze: I've once tried it to, perhaps the answer could give you some insights: codereview.stackexchange.com/questions/226781/…
• IEatBagels: @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

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.

• Carcigenicate: 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