Propagate bitmap from leaf -> root
My general idea is to build a bitmap of the values seen on each node, and propagate it towards the root. We can find the right most unset bit, as the 1st missin
My general idea is to build a bitmap of the values seen on each node, and propagate it towards the root. We can find the right most unset bit, as the 1st missing value for that node.\n\nThis approach works only because the **integer value is unbounded in Python3**, so I\'d highly recommend seeing other\'s approach to solve this problem that are more elegant than this.\n\n```\nimport math as m\n\nclass Solution:\n    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n        """\n            Create a bitmap of each node, and propagate it toward its parents with OR\n            Get the rightmost unset bit as the lowest missing value on each node.\n            \n        """\n        bits = [0 for _ in range(len(nums))]\n        result = [0 for _ in range(len(nums))]\n\n        # built an indegree mapping, we need to iterate from the leaf nodes upwards toward the root\n        indegree = [0 for _ in range(len(nums))]\n        no_indegree = set(i for i in range(len(nums)))\n        for parent in parents:\n            if parent != -1:\n                indegree[parent] += 1\n                if parent in no_indegree:\n                    no_indegree.remove(parent)\n            \n        \n        # Iterate from leaf nodes upwards to the root\n        no_indegree = list(no_indegree)\n        while no_indegree:\n            \n            current = no_indegree.pop()\n            value = nums[current]\n            \n            # Set the current bit with given nums for this node\n            bits[current] = bits[current] | 1 << (value-1)\n            \n            # Get the right most unset bit, use it as the result\n            n = bits[current]\n            result[current] = round(m.log((~n & (n+1))) / m.log(2)) + 1 \n            \n            # Propagate the bitmap to the parent, OR-ing with whatever bitmap the parent has\n            # If parent has multiple children, all the values seen by the children will be combined \n            parent = parents[current]\n            if parent != -1:\n                indegree[parent] -= 1\n                \n                # reduce indegree count of parent node, if it reached 0, add the parent node to the stack to be processed later\n                if indegree[parent] == 0:\n                    no_indegree.append(parent)\n                    \n                bits[parent] = bits[parent] | bits[current]\n                \n            # we\'ll hit memory limit if I don\'t cleanup like this\n            bits[current] = -1\n\n        return result\n```\n\n
[]