Problem Statement in English

You’re given a 2D integer array descriptions where descriptions[i] = [parent[i], child[i], isLeft[i]] indicates that parent[i] is the parent of child[i] in a binary tree. Additionally, isLeft[i] is 1 if child[i] is the left child of parent[i], and 0 if it’s the right child.

Construct the binary tree described by descriptions and return its root.

Approach

To solve this problem, we can use a hashmap to store the nodes of the binary tree. We will iterate through the descriptions array and for each description, we will create the parent and child nodes if they don’t already exist in the hashmap.

The simple way of finding the root is to use a set to keep track of all the nodes that are children. The node that is not a child of any other node will be the root.

But a more efficient and slightly more complex way is to keep track of the root node by using a variable that XORs the parent and child values. I had to look this part up.

Here’s how the mechanic works:

  • If we see a parent for the first time, we XOR it with the root variable.
  • If we see a child for the first time, we also XOR it with the root variable.
  • We XOR the root with the child again at the end of processing each description, which effectively cancels out the child from the root variable, leaving us with the root node at the end.

For example, let’s say we see a node as a parent first and then a child. The first time it’s XORed with the root variable, it will be added. The second time it’s XORed at the end of the loop, not whilst processing it as a child, and it will be removed, leaving us with the root node at the end.

And we’re done!

Solution in Python


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def createBinaryTree(self, des: List[List[int]]) -> Optional[TreeNode]:
        n = len(des)
        
        hm = {}
        root = 0

        for i in range(n):
            p, c, isLeft = des[i]

            if p not in hm:
                hm[p] = TreeNode(p)
                root ^= p
            
            if c not in hm:
                hm[c] = TreeNode(c)
                root ^= c

            root ^= c

            if isLeft:
                hm[p].left = hm[c]
            else:
                hm[p].right = hm[c]

        return hm[root]

Complexity

  • Time: $O(n)$
    Since we are iterating through the descriptions once, the time complexity is O(n).

  • Space: $O(n)$
    Since we are storing all the nodes in a hashmap, the space complexity is O(n).

And we are done.