> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Create Binary Tree From Descriptions

> Tested Python solution for LeetCode 2196 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 2196, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [Tree](/catalog/topics/tree), [Binary Tree](/catalog/topics/binary-tree). [View on LeetCode](https://leetcode.com/problems/create-binary-tree-from-descriptions/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2196   # by problem number
lcpy gen -s create_binary_tree_from_descriptions   # by problem name
```

## Problem

You are given a 2D integer array `descriptions` where `descriptions[i] = [parent<sub>i</sub>, child<sub>i</sub>, isLeft<sub>i</sub>]` indicates that `parent<sub>i</sub>` is the **parent** of `child<sub>i</sub>` in a **binary** tree of **unique** values. Furthermore,

* If `isLeft<sub>i</sub> == 1`, then `child<sub>i</sub>` is the left child of `parent<sub>i</sub>`.
* If `isLeft<sub>i</sub> == 0`, then `child<sub>i</sub>` is the right child of `parent<sub>i</sub>`.

Construct the binary tree described by `descriptions` and return its **root**.

The test cases will be generated such that the binary tree is **valid**.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2022/02/09/example1drawio.png)

```
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.
```

![Example 2](https://assets.leetcode.com/uploads/2022/02/09/example2drawio.png)

```
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.
```

### Constraints

* 1 \<= descriptions.length \<= 10^4
* descriptions\[i].length == 3
* 1 \<= parent\<sub>i\</sub>, child\<sub>i\</sub> \<= 10^5
* 0 \<= isLeft\<sub>i\</sub> \<= 1
* The binary tree described by descriptions is valid.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/create_binary_tree_from_descriptions/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/create_binary_tree_from_descriptions/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
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
```

## Complexity

| Time | Space |
| - | - |
| O(n) - one pass to link nodes, one pass over created nodes to find the root | O(n) - one TreeNode per unique value plus the children set |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.