Problem Description

You are given a 2D integer array descriptions where each element descriptions[i] = [parent_i, child_i, isLeft_i] represents a parent-child relationship in a binary tree with unique values.

The relationship is defined as:

• parent_i is the parent node of child_i
• If isLeft_i == 1, then child_i is the left child of parent_i
• If isLeft_i == 0, then child_i is the right child of parent_i

Your task is to construct the binary tree from these descriptions and return the root node of the tree.

The problem guarantees that the descriptions will form a valid binary tree.

Example Understanding:

If you have descriptions like [[20,15,1], [20,17,0], [50,20,1], [50,80,0]], this means:

• Node 20 has left child 15 and right child 17
• Node 50 has left child 20 and right child 80
• Node 50 is the root (since it appears as a parent but never as a child)

The key insight is that the root node will be the only node that appears as a parent but never as a child in any description.

Intuition

The main challenge is to build the tree from scattered parent-child relationships and identify which node is the root.

Let's think about what information we have:

• Each description tells us about one parent-child relationship
• We need to connect all these relationships to form a complete tree
• We need to find the root node

The key observation is: every node except the root will appear as a child in at least one description. The root node is special - it will only appear as a parent, never as a child.

This leads us to a two-step approach:

1. Build the tree structure: As we process each description, we need to create nodes if they don't exist yet and establish the parent-child connections. Using a hash table (nodes) makes it easy to check if a node already exists and to access any node by its value.

2. Find the root: We track all nodes that appear as children in a set (children). After processing all descriptions, the root will be the only node that exists in our nodes collection but is NOT in the children set. This is because the root has no parent, so it never appears as a child.

Why use defaultdict(TreeNode)? This clever trick allows us to automatically create a new TreeNode whenever we access a key that doesn't exist yet, simplifying our code. Though in the actual solution, we still check and create nodes explicitly for clarity.

The beauty of this approach is that we don't need to worry about the order of descriptions - we can process them in any order and still correctly build the tree and identify the root.

Learn more about Tree and Binary Tree patterns.

Solution Approach

We use a hash table-based approach to construct the binary tree from the given descriptions.

Data Structures Used:

• nodes: A hash table (dictionary) where keys are node values and values are TreeNode objects
• children: A set to track all nodes that appear as children

Step-by-step Implementation:

1. Initialize data structures:

   nodes = defaultdict(TreeNode)
   children = set()

2. Process each description: For each [parent, child, isLeft] in descriptions:

   a. Create or retrieve parent node:

   if parent not in nodes:
       nodes[parent] = TreeNode(parent)

   b. Create or retrieve child node:

   if child not in nodes:
       nodes[child] = TreeNode(child)

   c. Track child nodes:

   children.add(child)

   d. Establish parent-child relationship:

   if isLeft:
       nodes[parent].left = nodes[child]
   else:
       nodes[parent].right = nodes[child]

3. Find the root node: The root is the node that exists in nodes but not in children:

   root = (set(nodes.keys()) - children).pop()

   This set difference operation gives us exactly one element - the root node's value.

4. Return the root:

   return nodes[root]

Time Complexity: O(n) where n is the number of descriptions, as we iterate through the descriptions once and perform constant-time operations for each.

Space Complexity: O(n) for storing the nodes in the hash table and the children set.

The elegance of this solution lies in how it leverages the property that only the root node never appears as a child, making it easy to identify after building all the relationships.

Example Walkthrough

Let's walk through a small example with descriptions: [[1,2,1], [1,3,0], [2,4,1]]

This represents:

• Node 1 has left child 2
• Node 1 has right child 3
• Node 2 has left child 4

Step 1: Initialize data structures

• nodes = {} (empty dictionary)
• children = set() (empty set)

Step 2: Process first description [1,2,1]

• Parent = 1, Child = 2, isLeft = 1
• Node 1 doesn't exist, create it: nodes[1] = TreeNode(1)
• Node 2 doesn't exist, create it: nodes[2] = TreeNode(2)
• Add 2 to children set: children = {2}
• Since isLeft = 1, set left child: nodes[1].left = nodes[2]
• Current state: nodes = {1: TreeNode(1), 2: TreeNode(2)}, children = {2}

Step 3: Process second description [1,3,0]

• Parent = 1, Child = 3, isLeft = 0
• Node 1 already exists in nodes
• Node 3 doesn't exist, create it: nodes[3] = TreeNode(3)
• Add 3 to children set: children = {2, 3}
• Since isLeft = 0, set right child: nodes[1].right = nodes[3]
• Current state: nodes = {1: TreeNode(1), 2: TreeNode(2), 3: TreeNode(3)}, children = {2, 3}

Step 4: Process third description [2,4,1]

• Parent = 2, Child = 4, isLeft = 1
• Node 2 already exists in nodes
• Node 4 doesn't exist, create it: nodes[4] = TreeNode(4)
• Add 4 to children set: children = {2, 3, 4}
• Since isLeft = 1, set left child: nodes[2].left = nodes[4]
• Final state: nodes = {1: TreeNode(1), 2: TreeNode(2), 3: TreeNode(3), 4: TreeNode(4)}, children = {2, 3, 4}

Step 5: Find the root

• All nodes: {1, 2, 3, 4}
• Children nodes: {2, 3, 4}
• Root = nodes - children = {1, 2, 3, 4} - {2, 3, 4} = {1}
• Root value is 1

Step 6: Return the root node

• Return nodes[1], which is the TreeNode with value 1

The resulting tree structure:

      1
     / \
    2   3
   /
  4

Node 1 is correctly identified as the root because it's the only node that never appears as a child in any description.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of descriptions. Each description is processed exactly once in the for loop. Within the loop, all operations are constant time: checking if nodes exist in the dictionary, creating TreeNode objects, adding to a set, and assigning left/right children. The final operation of finding the root by computing the set difference set(nodes.keys()) - children takes O(n) time as it involves iterating through all nodes once.

The space complexity is O(n), where n is the length of descriptions. The nodes dictionary stores at most 2n unique nodes (in the worst case, each description introduces two unique nodes, though practically it's less due to shared nodes). The children set stores at most n child nodes (one per description). The TreeNode objects themselves also consume O(n) space. Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming Node Values Start from 0 or 1

A common mistake is assuming node values are sequential or start from a specific number. The problem states nodes have unique values, but they can be any integers.

Pitfall Example:

# WRONG: Assuming values are indices
nodes = [None] * len(descriptions)  # This won't work for arbitrary values

Solution: Use a dictionary/hash map to store nodes by their actual values:

nodes = {}  # Correct: Can handle any integer values

2. Creating Duplicate TreeNode Objects

Without checking if a node already exists, you might create multiple TreeNode objects for the same value, breaking the tree structure.

Pitfall Example:

# WRONG: Always creating new nodes
for parent_val, child_val, is_left in descriptions:
    parent = TreeNode(parent_val)  # Creates new node every time!
    child = TreeNode(child_val)    # Same issue here

Solution: Check if the node exists before creating:

if parent_val not in nodes:
    nodes[parent_val] = TreeNode(parent_val)
if child_val not in nodes:
    nodes[child_val] = TreeNode(child_val)

3. Not Handling the Case Where Parent Appears After Child

The descriptions might not be in order - a child node might appear as a parent in earlier descriptions before its own parent relationship is defined.

Pitfall Example:

# WRONG: Assuming parent nodes are always created before being referenced as children
# Given: [[15,10,1], [20,15,0]]  # 15 appears as parent before being defined as child

Solution: The hash map approach naturally handles this by creating nodes on-demand regardless of order.

4. Incorrectly Finding the Root Node

Some might try to find the root by looking for the first parent in descriptions or making assumptions about which node is the root.

Pitfall Example:

# WRONG: Assuming first parent is root
root = descriptions[0][0]  # Not necessarily the root!

# WRONG: Assuming largest/smallest value is root
root = max(nodes.keys())  # Arbitrary assumption

Solution: Use set difference to find the node that never appears as a child:

root_val = (set(nodes.keys()) - children).pop()

5. Memory Inefficiency with defaultdict

While the comment mentions using defaultdict, the actual code doesn't use it. If you do use it incorrectly, it can create unnecessary nodes.

Pitfall Example:

from collections import defaultdict
# WRONG: This creates TreeNode(0) for any accessed key
nodes = defaultdict(TreeNode)  # Creates nodes with val=0!

Solution: Either use a regular dictionary with existence checks (as shown in the solution) or use defaultdict with a lambda:

# Option 1: Regular dict (preferred for clarity)
nodes = {}
if parent_val not in nodes:
    nodes[parent_val] = TreeNode(parent_val)

# Option 2: defaultdict with lambda (more complex)
nodes = defaultdict(lambda: None)
# Still need to check and create properly