Create Binary Tree From Descriptions

medium tree array hash map binary tree

Problem

Each description is [parent, child, isLeft]. Build the binary tree and return its root.

Inputdescriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]

Outputroot with value 50

50 is the only value never appearing as a child.

descriptions (rows of "parent,child,isLeft" separated by ;)

def create_binary_tree(descriptions):
    nodes = {}
    is_child = set()
    for p, c, left in descriptions:
        if p not in nodes: nodes[p] = TreeNode(p)
        if c not in nodes: nodes[c] = TreeNode(c)
        if left:
            nodes[p].left = nodes[c]
        else:
            nodes[p].right = nodes[c]
        is_child.add(c)
    for v in nodes:
        if v not in is_child:
            return nodes[v]
    return None

function createBinaryTree(descriptions) {
  const nodes = new Map();
  const isChild = new Set();
  for (const [p, c, left] of descriptions) {
    if (!nodes.has(p)) nodes.set(p, { val: p, left: null, right: null });
    if (!nodes.has(c)) nodes.set(c, { val: c, left: null, right: null });
    if (left) nodes.get(p).left = nodes.get(c);
    else nodes.get(p).right = nodes.get(c);
    isChild.add(c);
  }
  for (const [v, node] of nodes) {
    if (!isChild.has(v)) return node;
  }
  return null;
}

class Solution {
    public TreeNode createBinaryTree(int[][] descriptions) {
        java.util.Map<Integer, TreeNode> nodes = new java.util.HashMap<>();
        java.util.Set<Integer> isChild = new java.util.HashSet<>();
        for (int[] d : descriptions) {
            int p = d[0], c = d[1];
            nodes.putIfAbsent(p, new TreeNode(p));
            nodes.putIfAbsent(c, new TreeNode(c));
            if (d[2] == 1) nodes.get(p).left = nodes.get(c);
            else nodes.get(p).right = nodes.get(c);
            isChild.add(c);
        }
        for (int v : nodes.keySet()) {
            if (!isChild.contains(v)) return nodes.get(v);
        }
        return null;
    }
}

TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
    unordered_map<int, TreeNode*> nodes;
    unordered_set<int> isChild;
    for (auto& d : descriptions) {
        int p = d[0], c = d[1];
        if (!nodes.count(p)) nodes[p] = new TreeNode(p);
        if (!nodes.count(c)) nodes[c] = new TreeNode(c);
        if (d[2] == 1) nodes[p]->left = nodes[c];
        else nodes[p]->right = nodes[c];
        isChild.insert(c);
    }
    for (auto& [v, node] : nodes) {
        if (!isChild.count(v)) return node;
    }
    return nullptr;
}

Explanation

We are handed a pile of rules like [parent, child, isLeft] and must wire them into a real tree, then hand back its root. The tricky bit is that the same value can show up in many rows, so we need a way to reuse the exact same node object every time we mention it.

The fix is a hash map from value to node. Whenever a row mentions a value, we look it up in nodes and create it only if it is not there yet. This guarantees one node per value, so attaching children always links the right objects.

For each row we connect the child to the parent: if isLeft is set we do parent.left = child, otherwise parent.right = child. At the same time we drop the child's value into an is_child set, recording that it has a parent.

The root is the one value that is never a child. So after processing all rows we scan the nodes and return the single one missing from is_child.

Example: [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]. The values that appear as children are 15, 17, 20, 80, 19; only 50 never does, so 50 is the root.

Time: O(n) Space: O(n)