0

My solution passes all cases, but I'm unsure what the runtime and space complexity would be. Would it be O(2^depth) since it recursively searches branches possibly spawning 2 more runs in each call? And I'm assuming its space complexity is O(n) where n = nodes in the tree? I'm really bad at wrapping my head around space/time complexity for recursive problems 

class Solution:    
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:

    def recurse(root, depth_dict, depth, parent):
        if root:
            depth_dict[root.val].append(depth)
            depth_dict[root.val].append(parent)

            if root.left or root.right:
                parent = root.val
                depth += 1

            recurse(root.left, depth_dict, depth, parent)
            recurse(root.right, depth_dict, depth, parent)


    depth_dict = defaultdict(list)  # first item = depth, 2nd item = parent
    depth = 0
    parent = None

    recurse(root, depth_dict, depth, parent)

    if depth_dict[x][0] == depth_dict[y][0] and depth_dict[x][1] != depth_dict[y][1]: 
        return True
    return False

In case that solution is O(2^d), I tried to write an O(n) solution:

def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
    def recurse(root, node, parent, depth):
        if root:
            if root.val == node:
                return depth, parent

            depth += 1
            return recurse(root.left, node, root.val, depth) or recurse(root.right, node, root.val, depth)

    depth_x, parent_x = recurse(root,x,None,0)
    depth_y, parent_y = recurse(root,y,None,0)

    if depth_x == depth_y and parent_x != parent_y:
        return True
    return False

This solution also passes and both are 64% faster than avg, so I'm a little confused, how are they the same runtime?

Another question I had about my 2nd solution was that it only worked when I had return recurse(root.left, node, root.val, depth) or recurse(root.right, node, root.val, depth) instead of 

recurse(root.left, node, root.val, depth) 
recurse(root.right, node, root.val, depth)

I don't really understand why the latter wouldn't work - I get the error TypeError: cannot unpack non-iterable NoneType object

user90823745
  • 149
  • 1
  • 2
  • 15
  • 1
    Leetcode's percentiles and timing is notoriously a rough estimate. I'd take it with a grain of salt and worry purely about the time complexity. Time complexity often requires massive input to impact the runtime, and then the machine, load and random luck are factors. People tend to view LC's time percentiles as a foolproof 100% guarantee of efficiency, and that's just not the case. As for your time complexity analyses, I think both algorithms are O(n) where n is the size of the tree. You're visiting every node one or two times (some constant factor), right? – ggorlen May 08 '20 at 00:07
  • @ggorlen Thanks for that heads up! And yea actually looking at my first solution I realize now why its O(n) and not O(2^d), whenever I see recursive I think of the fibonocci algo which is O(2^n) – user90823745 May 08 '20 at 17:40
  • 1
    The reason fib naive recursion without memoization is O(2^n) is that it repeatedly visits nodes again and again, which is not the case here. Visually, they look the same, but there's no overlapping visits in the algorithms you've shown here. I could post an answer here, but I just answered a similar question, so I'll try a dupe first even if it's not exactly the same. – ggorlen May 08 '20 at 17:44
  • Does this answer your question? [Time complexity of cloning a binary tree](https://stackoverflow.com/questions/61681299/time-complexity-of-cloning-a-binary-tree) – ggorlen May 08 '20 at 17:45
  • 1
    [This dupe one is even better](https://stackoverflow.com/questions/4547012/complexities-of-binary-tree-traversals) – ggorlen May 08 '20 at 17:46
  • 1
    @ggorlen your explanation and the link help, thanks so much! – user90823745 May 09 '20 at 00:09

0 Answers0