Create Binary Tree From Descriptions

Create Binary Tree From Descriptions

What is this problem about?

The Create Binary Tree From Descriptions interview question asks you to reconstruct a binary tree from a 2D array. Each element in the array is a description [parent, child, isLeft]. If isLeft is 1, the child is the left child of the parent; otherwise, it's the right child. Your task is to build the entire tree structure and return the root node.

Why is this asked in interviews?

Companies like Uber, Microsoft, and LinkedIn use this binary tree coding problem to test your ability to manage object references and identify tree roots. It evaluates how you handle node creation (ensuring you don't create multiple objects for the same value) and how you use auxiliary data structures like Hash Maps to store and retrieve existing nodes.

Algorithmic pattern used

This problem uses a Hash Table and Set approach.

1. Map for Nodes: Use a Hash Map to store nodeValue -> TreeNodeObject. If you encounter a value for the first time, create a new node and add it to the map.
2. Tracking Children: Use a Hash Set to store all values that appear as children.
3. Construction: Iterate through the descriptions, creating/retrieving the parent and child nodes, and linking them according to isLeft.
4. Finding Root: The root is the only node that appears as a parent but never as a child. Iterate through the parents and find the one not in the "Children Set."

Example explanation

Descriptions: [[1, 2, 1], [1, 3, 0], [2, 4, 1]]

1. Process [1, 2, 1]: Create node 1 and node 2. 1.left = 2. Child set: {2}.
2. Process [1, 3, 0]: Create node 3. 1.right = 3. Child set: {2, 3}.
3. Process [2, 4, 1]: Create node 4. 2.left = 4. Child set: {2, 3, 4}.
4. Candidates for root: {1, 2}.
5. 2 is in child set, 1 is NOT. Result: Node 1 is the root.

Common mistakes candidates make

• Duplicate Node Objects: Creating a new TreeNode for the same value every time it appears in the descriptions, which breaks the tree structure.
• Root Search Inefficiency: Performing a full traversal to find the root when a simple Set-based exclusion is much faster.
• Null Handling: Not checking if a node already exists in the map before creating a new one.

Interview preparation tip

Whenever you are asked to "construct" a graph or tree from a list of edges, a Hash Map of id -> node is your best friend. It allows you to link nodes by reference without losing access to them.