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

  • 1
    \$\begingroup\$ 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). \$\endgroup\$ Sep 30, 2019 at 16:57
  • 4
    \$\begingroup\$ 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. \$\endgroup\$
    – Reinderien
    Sep 30, 2019 at 18:26
  • \$\begingroup\$ 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. \$\endgroup\$
    – Turksarama
    Oct 1, 2019 at 3:11
  • \$\begingroup\$ I've once tried it to, perhaps the answer could give you some insights: codereview.stackexchange.com/questions/226781/… \$\endgroup\$
    – dfhwze
    Oct 1, 2019 at 6:27
  • \$\begingroup\$ @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 \$\endgroup\$
    – IEatBagels
    Oct 1, 2019 at 13:15

1 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.

  • 2
    \$\begingroup\$ 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 \$\endgroup\$ Oct 1, 2019 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.