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. ```hint Reuse node objects Map each value to one node, creating it on first sight. Attach child references as descriptions arrive. ``` ```hint Track child membership Record every value that appears as a child. After all attachments, the one mapped value outside that set is the root. ``` ### Example ```text 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?