Problem statement

https://binarysearch.com/problems/Search-in-a-Virtually-Complete-Binary-Tree/

Solution

We can first find path to given node if it exists and then check if we have path.

Complexity

It is O(log n) for time and space, where n = target.

Code

class Solution:
    def solve(self, root, target):
        if not target: return False
        path = [target]
        while path[-1] > 1:
            path += [path[-1]//2]
        path = path[::-1]
        
        for i in range(len(path) - 1):
            if path[i+1] == 2 * path[i]:
                if not root.left: return False
                root = root.left
            else:
                if not root.right: return False
                root = root.right
        return True