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^4descriptions[i].length == 31 <= parent, child <= 10^50 <= isLeft <= 1the descriptions describe a valid binary tree with distinct values
Hints for Create Binary Tree From Descriptions
Hint 1
Every value needs exactly one node object, however many descriptions mention it — keep a map from value to node.
Hint 2
Each description is then just one pointer to set on the parent's node.
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
- Create an empty map
value → nodeand an empty set of child values. - For each
[p, c, isLeft]: fetch or create the nodes forpandc, setp.left = corp.right = c, and addcto the set. - 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 NoneJava
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