Create Binary Tree From Descriptions

lcpy gen -n 2196   # by problem number
lcpy gen -s create_binary_tree_from_descriptions   # by problem name

Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
Output: [50,20,80,15,17,19]
Explanation: The root node is the node with value 50 since it has no parent.

Input: descriptions = [[1,2,1],[2,3,0],[3,4,1]]
Output: [1,2,null,null,3,4]
Explanation: The root node is the node with value 1 since it has no parent.

from leetcode_py import TreeNode


class Solution:
    # Time: O(n) - one pass to link nodes, one pass over created nodes to find the root
    # Space: O(n) - one TreeNode per unique value plus the children set
    def create_binary_tree(self, descriptions: list[list[int]]) -> TreeNode[int] | None:
        nodes: dict[int, TreeNode[int]] = {}
        children: set[int] = set()

        for parent, child, is_left in descriptions:
            if parent not in nodes:
                nodes[parent] = TreeNode(parent)
            if child not in nodes:
                nodes[child] = TreeNode(child)

            if is_left:
                nodes[parent].left = nodes[child]
            else:
                nodes[parent].right = nodes[child]
            children.add(child)

        for val, node in nodes.items():
            if val not in children:
                return node
        return None