2196. Create Binary Tree From Descriptions

Array
Hash Table
Tree
Binary Tree

TIME

O(n)

SPACE

O(n)

Intuition

Each description tells us a parent-child link. If we can quickly look up (or create) a node by its value, building the tree is just wiring those links together. The only real question is finding the root: it is the one value that is a parent but never a child.

Approach

Keep a hash map from value -> TreeNode, creating a node lazily the first time a value is seen.
Track the set of values that appear as a child.
For each [parent, child, isLeft]:
- get/create the parent and child nodes
- attach the child as the left or right child based on isLeft
- mark child as a seen child
The root is the single value present as a parent (a key in the map) that is never marked as a child.
Return that root node.

Complexity

Time: O(n), one pass over the descriptions; each node is touched a constant number of times
Space: O(n), the hash map of nodes and the child set

Edge Cases

Single description -> tree of two nodes, root is the parent
Same value appearing as parent in one row and child in another -> node reused via the map, not duplicated
Root determined purely by "parent but never child"; valid input guarantees exactly one

Code

from typing import List, Optional


# 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"]:
        """
        2196. Create Binary Tree From Descriptions
        Time: O(n)
        Space: O(n)
        """
        nodes = {}
        children = set()

        def get_node(value: int) -> "TreeNode":
            if value not in nodes:
                nodes[value] = TreeNode(value)
            return nodes[value]

        for parent, child, is_left in descriptions:
            parent_node = get_node(parent)
            child_node = get_node(child)

            if is_left == 1:
                parent_node.left = child_node
            else:
                parent_node.right = child_node

            children.add(child)

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

        return None

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 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;
 *     }
 * }
 */

/**
 * 2196. Create Binary Tree From Descriptions
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public TreeNode createBinaryTree(int[][] descriptions) {
        Map<Integer, TreeNode> nodes = new HashMap<>();
        Set<Integer> children = new HashSet<>();

        for (int[] description : descriptions) {
            int parent = description[0];
            int child = description[1];
            int isLeft = description[2];

            TreeNode parentNode = nodes.computeIfAbsent(parent, TreeNode::new);
            TreeNode childNode = nodes.computeIfAbsent(child, TreeNode::new);

            if (isLeft == 1) {
                parentNode.left = childNode;
            } else {
                parentNode.right = childNode;
            }

            children.add(child);
        }

        for (Map.Entry<Integer, TreeNode> entry : nodes.entrySet()) {
            if (!children.contains(entry.getKey())) {
                return entry.getValue();
            }
        }

        return null;
    }
}