1
\$\begingroup\$

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

\$\endgroup\$
  • 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\$ – Carcigenicate Sep 30 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 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 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 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 at 13:15
2
\$\begingroup\$

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.

\$\endgroup\$
  • 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\$ – Carcigenicate Oct 1 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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