Create a Binary Tree from Parent-Child Descriptions

Problem

Build a binary tree from parent-child descriptions. Each description is [parentValue, childValue, isLeft], where isLeft is 1 for a left child and 0 for a right child. Descriptions may arrive in any order, so intermediate records may form several partial trees.

Function Contract

Implement createBinaryTree(descriptions) and return the final root.

Constraints & Assumptions

• 1 <= len(descriptions) <= 100,000.
• Values are unique signed 32-bit integers.
• Input describes exactly one valid binary tree.
• Every child has exactly one parent, and each parent has at most one child on each side.

Clarifying Questions to Ask

• Are descriptions topologically ordered? No.
• Can a node appear as a child before it appears as a parent? Yes.
• How is the root identified? It is the only created node value never listed as a child.
• Can contradictory descriptions appear? No in the base input.

Example

descriptions = [[20,15,1], [20,17,0], [50,20,1], [50,80,0], [80,19,1]]
output root value = 50

Evaluation Focus

• Reuses one node identity per value.
• Works when parents and children arrive out of order.
• Finds the root without relying on input order.
• Runs in O(n) expected time and space.

Extensions to Discuss

1. How would you reject multiple parents or conflicting child slots?
2. How would you detect a cycle?
3. How could this be processed incrementally before the final description arrives?