Description
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
, thenchildi
is the left child ofparenti
. - If
isLefti == 0
, thenchildi
is the right child ofparenti
.
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:

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:

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.
Solution
C++
/**
* 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:
unordered_map<int, vector<pair<int, bool>>> graph;
unordered_map<int, int> indegree;
TreeNode* dfs(int val) {
TreeNode* node = new TreeNode(val);
for (const auto& [child, isLeft] : graph[val]) {
if (isLeft) node->left = dfs(child);
else node->right = dfs(child);
}
return node;
}
TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
graph.clear();
indegree.clear();
for (auto &desc : descriptions) {
auto parent = desc[0], child = desc[1], isLeft = desc[2];
graph[parent].push_back({child, isLeft});
indegree[child]++;
}
int root = -1;
for (auto &desc: descriptions) {
if (indegree[desc[0]] == 0) {
root = desc[0];
break;
}
}
return dfs(root);
}
};
Python3
# 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]:
graph = defaultdict(list)
indegree = defaultdict(int)
for parent, child, isLeft in descriptions:
graph[parent].append((child, isLeft))
indegree[child] += 1
root = -1
for parent, _, _ in descriptions:
if indegree[parent] == 0:
root = parent
break
assert root != -1
def dfs(val):
node = TreeNode(val)
for child, isLeft in graph[val]:
if isLeft:
node.left = dfs(child)
else:
node.right = dfs(child)
return node
return dfs(root)