Introduction

Binary tree construction problems are extremely common in coding interviews because they test multiple concepts together:

1. Tree data structures
2. HashMap usage
3. Parent-child relationships
4. Graph-style thinking
5. Root identification

LeetCode 2196 is an excellent medium-level problem that focuses on constructing a binary tree from parent-child descriptions efficiently.

In this article, we will deeply understand:

1. How the tree is formed
2. How to identify the root node
3. Why HashMap is useful here
4. Step-by-step dry run
5. Time and space complexity
6. Complete optimized Java solution

Problem Statement

You are given a 2D array:

Where:

1. parent is the parent node
2. child is the child node
3. isLeft == 1 means left child
4. isLeft == 0 means right child

Your task is to:

1. Construct the binary tree
2. Return the root node

Here is the Link to try it now -: Create Binary Tree From Descriptions

Example

Input

Output

Visual Representation

Key Observation

Every node except the root appears as a child exactly once.

This means:

1. Root node never appears in child positions
2. If we store all child nodes,
3. The node not present in the child set becomes the root

This is the core trick of the problem.

Approach Overview

We solve the problem in 3 steps:

Step 1: Find the Root Node

Store every child node in a HashSet.

Then iterate through descriptions again:

1. The parent that never appears as a child is the root.

Step 2: Create Tree Nodes

Use a HashMap:

This prevents duplicate node creation.

Step 3: Connect Parent and Child

Based on:

attach nodes accordingly.

Optimized Java Solution

Step-by-Step Explanation

Step 1: Store All Child Nodes

Every child is stored.

Since root never becomes a child,

it will not exist inside this set.

Step 2: Identify Root

This finds the node that only acts as parent.

That node becomes the root.

Step 3: Create Unique Tree Nodes

Avoids duplicate node creation.

Each value maps to exactly one TreeNode.

Step 4: Connect Parent and Child

or

depending on:

Dry Run

Input

Child Set

Root Detection

Check parents:

1. 20 → exists in child set
2. 50 → NOT in child set

So:

Tree Construction

50

1. left → 20
2. right → 80

20

1. left → 15
2. right → 17

80

1. left → 19

Final tree becomes:

Time Complexity

Building Child Set

Finding Root

Constructing Tree

Total Time Complexity

Efficient for large constraints.

Space Complexity

HashMap + HashSet

Why This Problem is Important

This problem teaches:

1. Tree construction
2. Parent-child mapping
3. Root identification
4. Efficient object reuse
5. HashMap optimization

It is frequently asked in interviews because it combines multiple concepts in one clean implementation.

Common Mistakes

1. Creating Duplicate Nodes

Wrong:

every time.

Always reuse nodes through HashMap.

2. Incorrect Root Detection

Remember:

Root never appears as child.

3. Forgetting Left vs Right Child

Always check:

before attaching.

Interview Tips

In interviews explain:

We first identify the root using a child set, then use a HashMap to create and reuse TreeNode objects efficiently while connecting parent-child relationships.

This demonstrates:

1. Strong data structure understanding
2. Efficient memory usage
3. Clean tree construction logic

Related Problems

Practice these next:

1. Construct Binary Tree from Traversals
2. Validate Binary Search Tree
3. Serialize and Deserialize Binary Tree
4. Lowest Common Ancestor
5. Binary Tree Level Order Traversal

Conclusion

LeetCode 2196 is a clean and elegant binary tree construction problem.

The major insight is:

The root node is the only node that never appears as a child.

Combined with HashMap-based node reuse, we can construct the entire tree efficiently in linear time.

This is an excellent interview problem for mastering tree construction patterns.