Easy Python | O(1) Find | Recursion + Queue
Easy Python | O(1) Find | Recursion + Queue\n\nA) Standard Code\n\nIn this problem, we can recover the values of the original Binary Tree, and store them in a "
**Easy Python | O(1) Find | Recursion + Queue**\n\n**A) Standard Code**\n\nIn this problem, we can recover the values of the original Binary Tree, and store them in a "set" directly. (There\'s no need to keep the Binary Tree itself)\n\nThis way, we can "find" any element with O(1) time/space complexity. The initialization method still runs with O(n) time/space complexity though.\n\n```\nclass FindElements(object):\n    def __init__(self, root):\n        self.A = A = set()\n        #\n        def recover(n,x):\n            if n:\n                A.add(x)\n                recover(n.left , 2*x + 1)\n                recover(n.right, 2*x + 2)\n        #\n        recover(root,0)\n    #\n    def find(self, target):\n        return target in self.A\n```\n\n**B) 4 Lines of Code**\n\nOne-Liner version of the "Recover" function :)\n\n```\nclass FindElements:\n    def __init__(self, root):\n        self.A = A = set()\n        recover = lambda n,x: [ A.add(x) , recover(n.left,2*x+1) , recover(n.right,2*x+2) ] if n else None\n        recover(root,0)\n    def find(self, target):\n        return target in self.A\n```\n\n**C) Queue Method**\n\nThe previous code versions work fine. However, recursion consumes a lot of system resources, due to the initialization, namespace, and environment variables of each function call. Besides, many compilers have a hardcoded limit for Max. Recursion Depth, and there can be complicaitons by constantly needing to edit global settings.\n\nThere\'s still hope in the galaxy though. We can use "Queues" to traverse the original Binary Tree without applying recursion.\n\nHere\'s the code:\n\n```\n# C) Improved Function without Recursion\nclass FindElements:\n    def __init__(self, root):\n        self.A = A = set()\n        # ---------------------------------------------------------------\n        #     Queue Version of the Binary Tree "Recovery" Method \n        # ---------------------------------------------------------------\n        if not root:\n            return\n        #\n        queue = collections.deque([[root,0]])\n        while queue:\n            n,x = queue.popleft()\n            A.add(x)\n            if n.left:\n                queue.append( [n.left  , 2*x+1] )\n            if n.right:\n                queue.append( [n.right , 2*x+2] )\n    #\n    def find(self, target):\n        return target in self.A\n```\n\nI hope the code was helpful. Cheers,\n
['Python', 'Python3']