Create Binary Tree From Descriptions - Video Solutions

Problem Overview: You receive a list of descriptions where each entry contains [parent, child, isLeft]. The task is to construct the binary tree represented by these relationships and return the root node. Each pair tells you the parent value, the child value, and whether the child is the left or right node.

Approach 1: Hash Map to Track Parent-Child Relationships (O(n) time, O(n) space)

The main challenge is that nodes may appear in any order, so you cannot assume the parent node already exists when processing a description. Use a hash map that maps node values to actual TreeNode objects. Iterate through the descriptions array once, creating nodes if they do not already exist. For every entry, link the child node to the parent node based on the isLeft flag. At the same time, track all values that appear as children using a set. After processing all descriptions, the root is the node that never appeared as a child. This approach performs constant-time hash lookups for node creation and linking, making the entire process linear.

This method works well because it decouples node creation from tree structure. You simply ensure every value maps to exactly one node object, then connect them using the relationships provided. Hash-based lookup avoids repeated scans and ensures each description is processed once.

Approach 2: Linking Nodes Using Two-Pass Array (O(n) time, O(n) space)

Another strategy separates node creation and node linking into two passes. During the first pass, iterate through the descriptions and create node objects for every unique value you encounter. Store them in an indexed structure or hash map for quick access. In the second pass, iterate again and connect children to parents using the isLeft flag. Maintain a boolean array or set to mark nodes that appear as children. After linking, the root is the node that was never marked as a child.

This approach keeps the logic straightforward by avoiding conditional node creation while linking. The first pass guarantees all nodes exist, and the second pass strictly focuses on building the edges. The complexity remains linear because each description is processed a constant number of times.

Both approaches rely heavily on efficient lookups using structures from hash tables and sequential processing of the array input. The final structure produced is a standard binary tree.

Recommended for interviews: The hash map approach is the expected solution. It constructs nodes and links them in a single pass while tracking the root using a child set. Showing the two-pass method demonstrates clarity in separating responsibilities, but the single-pass hash map version highlights stronger algorithmic efficiency and cleaner reasoning.