# Create Binary Tree From Descriptions
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/create-binary-tree-from-descriptions)
Canonical: https://scaleengineer.com/dsa/problems/create-binary-tree-from-descriptions
**Data structures:** Array, Hash Table, Tree, Binary Tree
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin), [Clari](https://scaleengineer.com/companies/clari)
---
## Problem
You are given a 2D integer array `descriptions` where `descriptions[i] = [parenti, childi, isLefti]` indicates that `parenti` is the **parent** of `childi` in a **binary** tree of **unique** values. Furthermore,

* If `isLefti == 1`, then `childi` is the left child of `parenti`.
* If `isLefti == 0`, then `childi` is the right child of `parenti`.

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

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

**Example 1:**

![](https://assets.glich.co/dsa/create-binary-tree-from-descriptions/image0.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.
The resulting binary tree is shown in the diagram.

**Example 2:**

![](https://assets.glich.co/dsa/create-binary-tree-from-descriptions/image1.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.
The resulting binary tree is shown in the diagram.

**Constraints:**

* `1 <= descriptions.length <= 104`
* `descriptions[i].length == 3`
* `1 <= parenti, childi <= 105`
* `0 <= isLefti <= 1`
* The binary tree described by `descriptions` is valid.

# Approaches
## Two-Pass Approach with HashMap and HashSet
This approach separates the problem into two distinct phases: first, building the complete tree structure, and second, identifying the root node. It uses a HashMap to keep track of created nodes to avoid duplicates and a HashSet to record all nodes that are children. The root is then found by identifying a parent node that never appears in the set of children.
**Time:** O(N), where N is the number of descriptions. The first pass iterates through all N descriptions, and the map/set operations take average O(1) time. The second pass also iterates through N descriptions. Thus, the total time is O(N + N) = O(N). · **Space:** O(M), where M is the number of unique nodes in the tree. The `HashMap` stores a `TreeNode` for each of the M unique nodes, and the `HashSet` stores all child values (at most M-1).
**Pros:** Conceptually straightforward and easy to implement.; Reliably constructs the tree and finds the root by clearly separating concerns.
**Cons:** Requires two full passes over the input `descriptions` array, making it slightly less efficient than a single-pass solution.
### Explanation
This approach involves two main stages. First, we construct the entire tree structure, and second, we identify the root node.

*   **Data Structures:** We use two primary data structures:
    *   A `HashMap<Integer, TreeNode>` to store each unique node. The key is the node's integer value, and the value is the `TreeNode` object itself. This allows for O(1) average time access to any node by its value, preventing us from creating duplicate nodes.
    *   A `HashSet<Integer>` to keep track of all values that appear as a child in any description. This set will be crucial for identifying the root later.

*   **Pass 1: Tree Construction:**
    *   We iterate through every description `[parent, child, isLeft]` in the input array.
    *   For each description, we ensure that both the parent and child nodes exist in our `nodeMap`. If a node for a given value isn't in the map, we create a new `TreeNode` and add it.
    *   We then retrieve the `parentNode` and `childNode` objects from the map.
    *   Based on the `isLeft` flag (1 for left, 0 for right), we establish the parent-child relationship: `parentNode.left = childNode` or `parentNode.right = childNode`.
    *   Finally, we add the `child`'s value to our `children` set.

*   **Pass 2: Root Identification:**
    *   After the first pass, all nodes are created and linked, and we have a complete set of all child nodes. The root of the tree is the only node that is a parent but never a child.
    *   We can find this node by iterating through the `descriptions` array a second time. For each `parent` value, we check if it's present in our `children` set.
    *   The first `parent` value we encounter that is *not* in the `children` set must be the root. We then retrieve its corresponding `TreeNode` from the `nodeMap` and return it.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode createBinaryTree(int[][] descriptions) {
        Map<Integer, TreeNode> nodeMap = new HashMap<>();
        Set<Integer> children = new HashSet<>();

        // Pass 1: Build the tree structure and identify all children
        for (int[] desc : descriptions) {
            int parentVal = desc[0];
            int childVal = desc[1];
            boolean isLeft = desc[2] == 1;

            nodeMap.putIfAbsent(parentVal, new TreeNode(parentVal));
            nodeMap.putIfAbsent(childVal, new TreeNode(childVal));

            TreeNode parentNode = nodeMap.get(parentVal);
            TreeNode childNode = nodeMap.get(childVal);
            if (isLeft) {
                parentNode.left = childNode;
            } else {
                parentNode.right = childNode;
            }

            children.add(childVal);
        }

        // Pass 2: Find the root
        TreeNode root = null;
        for (int[] desc : descriptions) {
            int parentVal = desc[0];
            if (!children.contains(parentVal)) {
                root = nodeMap.get(parentVal);
                break; 
            }
        }
        
        return root;
    }
}
```
### Algorithm
- Initialize a `HashMap<Integer, TreeNode>` to map node values to `TreeNode` objects.
- Initialize a `HashSet<Integer>` to store the values of all child nodes.
- **First Pass (Build Tree & Identify Children):** Iterate through each `description` `[parent, child, isLeft]`.
  - For both `parent` and `child` values, if they are not already in the map, create a new `TreeNode` and add it to the map.
  - Retrieve the `parentNode` and `childNode` from the map.
  - Link them: if `isLeft` is 1, `parentNode.left = childNode`; otherwise, `parentNode.right = childNode`.
  - Add the `child` value to the `children` set.
- **Second Pass (Find Root):** Iterate through each `description` again.
  - Check if the `parent` value from the current description exists in the `children` set.
  - If it does not, this `parent` is the root.
  - Return the `TreeNode` corresponding to this root value from the map.

## Optimized Single-Pass Approach
This approach optimizes the process by building the tree and identifying all child nodes in a single pass over the input descriptions. After this pass, the `nodeMap` contains all the nodes and the `childrenSet` contains all nodes with a parent. The root is then found by identifying the single node in the map that is not in the children set.
**Time:** O(N), where N is the number of descriptions. We iterate through the `descriptions` array once (O(N)). Then, we iterate through the unique nodes in the `nodeMap` to find the root. The number of unique nodes, M, is at most 2*N. So the total time complexity is O(N + M) which simplifies to O(N). · **Space:** O(M), where M is the number of unique nodes. We use a `HashMap` to store M nodes and a `HashSet` to store up to M-1 child nodes. The space is proportional to the number of unique nodes.
**Pros:** More efficient than the two-pass approach as it processes the input array only once to build the tree structure.; Maintains the same clear logic of using a map for nodes and a set for children.; Code can be made very concise using methods like `computeIfAbsent`.
**Cons:** Still requires extra space for the `HashSet` and a second loop (over the map's keys) to find the root after the main processing loop.
### Explanation
This approach improves on the two-pass method by combining tree construction and data gathering into a single, more efficient pass.

*   **Algorithm:**
    1.  **Initialization:** We start by initializing a `HashMap<Integer, TreeNode>` named `nodeMap` to map node values to their respective `TreeNode` objects and a `HashSet<Integer>` named `childrenSet` to record all node values that are children.
    2.  **Single Pass:** We iterate through the `descriptions` array just once. For each `[parentVal, childVal, isLeft]` entry:
        *   We use `nodeMap.computeIfAbsent(value, k -> new TreeNode(k))` for both `parentVal` and `childVal`. This is a concise way to get the `TreeNode` if it exists or create and add it to the map if it doesn't.
        *   We retrieve the `parentNode` and `childNode` objects.
        *   We connect them according to the `isLeft` flag: `parentNode.left = childNode` or `parentNode.right = childNode`.
        *   We add `childVal` to the `childrenSet`.
    3.  **Root Finding:** After the loop completes, `nodeMap` contains all the nodes of the tree, and `childrenSet` contains all the nodes that have a parent. By definition, the root is the only node in the tree that does not have a parent.
    4.  Therefore, we can find the root by iterating through all the node values present in `nodeMap.keySet()`. The first value we find that is *not* contained in `childrenSet` is the value of the root node.
    5.  We then return the `TreeNode` corresponding to this root value from `nodeMap`. Given the problem's guarantee of a valid tree, a single unique root is guaranteed to be found.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode createBinaryTree(int[][] descriptions) {
        Map<Integer, TreeNode> nodeMap = new HashMap<>();
        Set<Integer> childrenSet = new HashSet<>();

        // Single pass to build the tree and populate the children set
        for (int[] description : descriptions) {
            int parentVal = description[0];
            int childVal = description[1];
            boolean isLeft = description[2] == 1;

            TreeNode parentNode = nodeMap.computeIfAbsent(parentVal, k -> new TreeNode(k));
            TreeNode childNode = nodeMap.computeIfAbsent(childVal, k -> new TreeNode(k));

            if (isLeft) {
                parentNode.left = childNode;
            } else {
                parentNode.right = childNode;
            }
            
            childrenSet.add(childVal);
        }

        // Find the root: the node that is never a child
        for (int nodeVal : nodeMap.keySet()) {
            if (!childrenSet.contains(nodeVal)) {
                return nodeMap.get(nodeVal);
            }
        }

        return null; // Should not be reached
    }
}
```
### Algorithm
- Initialize a `HashMap<Integer, TreeNode>` called `nodeMap` to store created nodes.
- Initialize a `HashSet<Integer>` called `childrenSet` to store the values of all child nodes.
- **Single Pass (Build Tree & Track Children):** Iterate through each `description` `[parentVal, childVal, isLeft]`.
  - Get or create the parent and child nodes using `nodeMap.computeIfAbsent()`.
  - Retrieve the `parentNode` and `childNode` from `nodeMap`.
  - Link the nodes based on `isLeft`.
  - Add `childVal` to the `childrenSet`.
- **Find Root:** After the loop, iterate through the keys in `nodeMap`.
  - The first key (node value) that is not found in `childrenSet` is the root's value.
  - Return the `TreeNode` associated with this root value from `nodeMap`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode createBinaryTree ( int [][] descriptions ) { Map < Integer , TreeNode > m = new HashMap <>(); Set < Integer > vis = new HashSet <>(); for ( int [] d : descriptions ) { int p = d [ 0 ], c = d [ 1 ], isLeft = d [ 2 ]; if (! m . containsKey ( p )) { m . put ( p , new TreeNode ( p )); } if (! m . containsKey ( c )) { m . put ( c , new TreeNode ( c )); } if ( isLeft == 1 ) { m . get ( p ). left = m . get ( c ); } else { m . get ( p ). right = m . get ( c ); } vis . add ( c ); } for ( Map . Entry < Integer , TreeNode > entry : m . entrySet ()) { if (! vis . contains ( entry . getKey ())) { return entry . getValue (); } } return null ; } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {number[][]} descriptions * @return {TreeNode} */ var createBinaryTree =
  function (descriptions) {
    const nodes = {};
    const children = new Set();
    for (const [parent, child, isLeft] of descriptions) {
      if (!nodes[parent]) {
        nodes[parent] = new TreeNode(parent);
      }
      if (!nodes[child]) {
        nodes[child] = new TreeNode(child);
      }
      if (isLeft) {
        nodes[parent].left = nodes[child];
      } else {
        nodes[parent].right = nodes[child];
      }
      children.add(child);
    }
    for (const [k, v] of Object.entries(nodes)) {
      if (!children.has(+k)) {
        return v;
      }
    }
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * createBinaryTree ( vector < vector < int >>& descriptions ) { unordered_map < int , TreeNode *> m ; unordered_set < int > vis ; for ( auto & d : descriptions ) { int p = d [ 0 ], c = d [ 1 ], left = d [ 2 ]; if ( ! m . count ( p )) m [ p ] = new TreeNode ( p ); if ( ! m . count ( c )) m [ c ] = new TreeNode ( c ); if ( left ) m [ p ] -> left = m [ c ]; else m [ p ] -> right = m [ c ]; vis . insert ( c ); } for ( auto & [ v , node ] : m ) { if ( ! vis . count ( v )) return node ; } return nullptr ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def createBinaryTree ( self , descriptions : List [ List [ int ]]) -> Optional [ TreeNode ]: g = defaultdict ( TreeNode ) vis = set () for p , c , left in descriptions : if p not in g : g [ p ] = TreeNode ( p ) if c not in g : g [ c ] = TreeNode ( c ) if left : g [ p ]. left = g [ c ] else : g [ p ]. right = g [ c ] vis . add ( c ) for v , node in g . items (): if v not in vis : return node
```