Create Binary Tree From Descriptions

Medium
1955.

Create Binary Tree From Descriptions

Create Binary Tree From Descriptions is a medium coding problem on arrays, hash table and trees, asked in Amazon, Google and Microsoft interviews.

You are given a 2D array descriptions where descriptions[i] = [parent, child, isLeft] says that the node with value parent has the node with value child as its left child when isLeft == 1, or as its right child when isLeft == 0. All node values are distinct.

The descriptions together form one valid binary tree. Build it and return its root.

Example 1

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
50 is never anyone's child, so it is the root; 20 and 80 are its children, and so on.

Example 2

Input
descriptions = [[1,2,1],[2,3,0],[3,4,1]]
Output
[1,2,null,null,3,4]
Explanation
A zigzag chain: 2 is 1's left child, 3 is 2's right child, 4 is 3's left child.

Example 3

Input
descriptions = [[7,3,0]]
Output
[7,null,3]
Explanation
One edge: 3 is the right child of the root 7.

Constraints

  • 1 <= descriptions.length <= 10^4
  • descriptions[i].length == 3
  • 1 <= parent, child <= 10^5
  • 0 <= isLeft <= 1
  • the descriptions describe a valid binary tree with distinct values
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * 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) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Create Binary Tree From Descriptions — Problem & Solution

Create Binary Tree From Descriptions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Create Binary Tree From Descriptions is a medium coding problem on arrays, hash table and trees, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Trees
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a 2D array descriptions where descriptions[i] = [parent, child, isLeft] says that the node with value parent has the node with value child as its left child when isLeft == 1, or as its right child when isLeft == 0. All node values are distinct.

The descriptions together form one valid binary tree. Build it and return its root.

Example 1

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: 50 is never anyone's child, so it is the root; 20 and 80 are its children, and so on.

Example 2

Input: descriptions = [[1,2,1],[2,3,0],[3,4,1]]
Output: [1,2,null,null,3,4]
Explanation: A zigzag chain: 2 is 1's left child, 3 is 2's right child, 4 is 3's left child.

Example 3

Input: descriptions = [[7,3,0]]
Output: [7,null,3]
Explanation: One edge: 3 is the right child of the root 7.

Constraints

  • 1 <= descriptions.length <= 10^4
  • descriptions[i].length == 3
  • 1 <= parent, child <= 10^5
  • 0 <= isLeft <= 1
  • the descriptions describe a valid binary tree with distinct values

Hints for Create Binary Tree From Descriptions

  1. Hint 1

    Every value needs exactly one node object, however many descriptions mention it — keep a map from value to node.

  2. Hint 2

    Each description is then just one pointer to set on the parent's node.

  3. Hint 3

    The root is the one parent value that never appears as a child; record every child value in a set and look for the parent that is missing from it.

How to solve Create Binary Tree From Descriptions

Map each value to a single node, wire up the pointers description by description, and pick as root the only node that is never someone's child.

Approach

  1. Create an empty map value → node and an empty set of child values.
  2. For each [p, c, isLeft]: fetch or create the nodes for p and c, set p.left = c or p.right = c, and add c to the set.
  3. Scan the parents; the one not in the child set is the root. Return its node.

Why it works

Using one node per value makes every description refer to the same objects, so the pointers assemble into the described tree. In a tree every node except the root has exactly one parent, so the root is precisely the value that never occurs as a child, and it occurs as a parent because the tree has at least one edge.

Complexity

  • Time — O(n) expected with a hash map
  • Space — O(n)

Pitfalls

  • Creating a new node every time a value appears splits one node into several disconnected copies.
  • Do not assume the first description's parent is the root — the descriptions come in any order.

Reference solution

Python

from typing import List, Optional

def createBinaryTree(descriptions: List[List[int]]) -> Optional[TreeNode]:
    nodes = {}
    children = set()
    for p, c, is_left in descriptions:
        if p not in nodes:
            nodes[p] = TreeNode(p)
        if c not in nodes:
            nodes[c] = TreeNode(c)
        if is_left == 1:
            nodes[p].left = nodes[c]
        else:
            nodes[p].right = nodes[c]
        children.add(c)
    for p, _, _ in descriptions:
        if p not in children:
            return nodes[p]
    return None

Java

public static TreeNode createBinaryTree(int[][] descriptions) {
    Map<Integer, TreeNode> nodes = new HashMap<>();
    Set<Integer> children = new HashSet<>();
    for (int[] d : descriptions) {
        TreeNode p = nodes.computeIfAbsent(d[0], TreeNode::new);
        TreeNode c = nodes.computeIfAbsent(d[1], TreeNode::new);
        if (d[2] == 1) p.left = c; else p.right = c;
        children.add(d[1]);
    }
    for (int[] d : descriptions) if (!children.contains(d[0])) return nodes.get(d[0]);
    return null;
}

C++

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

JavaScript

var createBinaryTree = function(descriptions) {
    var nodes = new Map(), children = new Set();
    var get = function(v) {
        var n = nodes.get(v);
        if (n === undefined) { n = new TreeNode(v); nodes.set(v, n); }
        return n;
    };
    for (var i = 0; i < descriptions.length; i++) {
        var d = descriptions[i];
        if (d[2] === 1) get(d[0]).left = get(d[1]); else get(d[0]).right = get(d[1]);
        children.add(d[1]);
    }
    for (var j = 0; j < descriptions.length; j++) {
        if (!children.has(descriptions[j][0])) return nodes.get(descriptions[j][0]);
    }
    return null;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets