Create Binary Tree From Descriptions solution and explanation
Google
9 more videos on this problem
Create Binary Tree From Descriptions | Simplest Approach | Leetcode 2196 | codestorywithMIKcodestorywithMIK · 19:14 · 14K views
Create Binary Tree from Descriptions - Leetcode 2196 - PythonNeetCodeIO · 9:50 · 14K views
2196. Create Binary Tree From Descriptions | Tree | Hash Map @codeWithAryanBhaiAryan Mittal · 7:32 · 4K views
Create Binary Tree from Descriptions - Leetcode 2196 - JavaAli Bouali · 14:08 · 1K views
2196. Create Binary Tree From Descriptions (Leetcode Medium)Programming Live with Larry · 7:09 · 386 views
2196. Create Binary Tree From Descriptions | Leetcode Daily - PythonLeetcode Daily · 5:11 · 377 views
Create Binary Tree From Descriptions | LeetCode 2196 | Medium | Complete ExplanationStreak To Scale · 3:28 · 301 views
LeetCode 2196 - Create Binary Tree From Description - JavaAlpha-Code · 13:15 · 105 views
2196. Create Binary Tree From Descriptions | POTD 7 June 2026 | C++ | LeetcodeTechie On Track · 10:38 · 56 views
Leetcode 2196. Create Binary Tree From DescriptionsExpertFunda · 11:06 · 54 views
The problem
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, thenchildiis the left child ofparenti. - If
isLefti == 0, thenchildiis 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 <= 104descriptions[i].length == 31 <= parenti, childi <= 1050 <= isLefti <= 1- The binary tree described by
descriptionsis valid.
Approach overview
Problem Overview: You receive a list of descriptions where each entry contains [parent, child, isLeft]. The task is to construct the binary tree represented by these relationships and return the root node. Each pair tells you the parent value, the child value, and whether the child is the left or right node.
Approach 1: Hash Map to Track Parent-Child Relationships (O(n) time, O(n) space)
The main challenge is that nodes may appear in any order, so you cannot assume the parent node already exists when processing a description. Use a hash map that maps node values to actual TreeNode objects. Iterate through the descriptions array once, creating nodes if they do not already exist. For every entry, link the child node to the parent node based on the isLeft flag. At the same time, track all values that appear as children using a set. After processing all descriptions, the root is the node that never appeared as a child. This approach performs constant-time hash lookups for node creation and linking, making the entire process linear.
This method works well because it decouples node creation from tree structure. You simply ensure every value maps to exactly one node object, then connect them using the relationships provided. Hash-based lookup avoids repeated scans and ensures each description is processed once.
Approach 2: Linking Nodes Using Two-Pass Array (O(n) time, O(n) space)
Another strategy separates node creation and node linking into two passes. During the first pass, iterate through the descriptions and create node objects for every unique value you encounter. Store them in an indexed structure or hash map for quick access. In the second pass, iterate again and connect children to parents using the isLeft flag. Maintain a boolean array or set to mark nodes that appear as children. After linking, the root is the node that was never marked as a child.
This approach keeps the logic straightforward by avoiding conditional node creation while linking. The first pass guarantees all nodes exist, and the second pass strictly focuses on building the edges. The complexity remains linear because each description is processed a constant number of times.
Both approaches rely heavily on efficient lookups using structures from hash tables and sequential processing of the array input. The final structure produced is a standard binary tree.
Recommended for interviews: The hash map approach is the expected solution. It constructs nodes and links them in a single pass while tracking the root using a child set. Showing the two-pass method demonstrates clarity in separating responsibilities, but the single-pass hash map version highlights stronger algorithmic efficiency and cleaner reasoning.
Approach 1: Hash Map to Track Parent-Child Relationships
This approach uses a hash map to create nodes and establish their parent-child relationships. The root node is determined by finding nodes that haven't been a child in any relationship.
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):
nodeMap = {}
children = set()
for parent, child, isLeft in descriptions:
if parent not in nodeMap:
nodeMap[parent] = TreeNode(parent)
if child not in nodeMap:
nodeMap[child] = TreeNode(child)
if isLeft:
nodeMap[parent].left = nodeMap[child]
else:
nodeMap[parent].right = nodeMap[child]
children.add(child)
# Find the root
for key in nodeMap:
if key not in children:
return nodeMap[key]
return Noneimport java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}
class Solution {
public TreeNode createBinaryTree(int[][] descriptions) {
Map<Integer, TreeNode> nodeMap = new HashMap<>();
Set<Integer> children = new HashSet<>();
for (int[] desc : descriptions) {
int parent = desc[0], child = desc[1], isLeft = desc[2];
nodeMap.putIfAbsent(parent, new TreeNode(parent));
nodeMap.putIfAbsent(child, new TreeNode(child));
if (isLeft == 1) {
nodeMap.get(parent).left = nodeMap.get(child);
} else {
nodeMap.get(parent).right = nodeMap.get(child);
}
children.add(child);
}
for (int key : nodeMap.keySet()) {
if (!children.contains(key)) {
return nodeMap.get(key);
}
}
return null;
}
}#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
unordered_map<int, TreeNode*> nodes;
unordered_set<int> children;
for (const auto& desc : descriptions) {
int parent = desc[0], child = desc[1], isLeft = desc[2];
if (nodes.find(parent) == nodes.end())
nodes[parent] = new TreeNode(parent);
if (nodes.find(child) == nodes.end())
nodes[child] = new TreeNode(child);
if (isLeft) {
nodes[parent]->left = nodes[child];
} else {
nodes[parent]->right = nodes[child];
}
children.insert(child);
}
for (const auto& [key, node] : nodes) {
if (children.find(key) == children.end()) {
return node;
}
}
return nullptr;
}
};class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function createBinaryTree(descriptions) {
const nodeMap = new Map();
const children = new Set();
for (const [parent, child, isLeft] of descriptions) {
if (!nodeMap.has(parent)) {
nodeMap.set(parent, new TreeNode(parent));
}
if (!nodeMap.has(child)) {
nodeMap.set(child, new TreeNode(child));
}
if (isLeft === 1) {
nodeMap.get(parent).left = nodeMap.get(child);
} else {
nodeMap.get(parent).right = nodeMap.get(child);
}
children.add(child);
}
for (const [key, node] of nodeMap) {
if (!children.has(key)) {
return node;
}
}
return null;
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
TreeNode* createBinaryTree(int** descriptions, int descriptionsSize, int* descriptionsColSize) {
TreeNode* nodes[100000] = { NULL };
bool isChild[100000] = { false };
for (int i = 0; i < descriptionsSize; ++i) {
int parentVal = descriptions[i][0], childVal = descriptions[i][1], isLeft = descriptions[i][2];
if (nodes[parentVal] == NULL) {
nodes[parentVal] = createNode(parentVal);
}
if (nodes[childVal] == NULL) {
nodes[childVal] = createNode(childVal);
}
if (isLeft) {
nodes[parentVal]->left = nodes[childVal];
} else {
nodes[parentVal]->right = nodes[childVal];
}
isChild[childVal] = true;
}
for (int i = 0; i < 100000; ++i) {
if (nodes[i] != NULL && !isChild[i]) {
return nodes[i]; // This node is not a child, hence it must be the root
}
}
return NULL;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public TreeNode CreateBinaryTree(int[][] descriptions) {
Dictionary<int, TreeNode> nodeMap = new Dictionary<int, TreeNode>();
HashSet<int> children = new HashSet<int>();
foreach (var desc in descriptions) {
int parent = desc[0], child = desc[1], isLeft = desc[2];
if (!nodeMap.ContainsKey(parent)) {
nodeMap[parent] = new TreeNode(parent);
}
if (!nodeMap.ContainsKey(child)) {
nodeMap[child] = new TreeNode(child);
}
if (isLeft == 1) {
nodeMap[parent].left = nodeMap[child];
} else {
nodeMap[parent].right = nodeMap[child];
}
children.Add(child);
}
foreach (var key in nodeMap.Keys) {
if (!children.Contains(key)) {
return nodeMap[key];
}
}
return null;
}
}The Python solution leverages a dictionary to track TreeNode instances and a set to identify nodes that have appeared as children. It iteratively constructs the tree based on the input descriptions, following direct mapping and reference updates.
Time Complexity: O(N), where N is the number of descriptions.
Space Complexity: O(V), where V is the number of unique nodes.
Approach 2: Linking Nodes Using Two-Pass Array
This approach uses a two-pass algorithm: the first pass creates all nodes independently, and the second pass links them based on the descriptive relationships. This avoids simultaneous creation and linking, providing a clearer separation of concerns between node creation and linkage.
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):
nodeMap = {}
children = set()
# First pass: Create all nodes
for parent, child, isLeft in descriptions:
if parent not in nodeMap:
nodeMap[parent] = TreeNode(parent)
if child not in nodeMap:
nodeMap[child] = TreeNode(child)
children.add(child)
# Second pass: Link nodes
for parent, child, isLeft in descriptions:
if isLeft:
nodeMap[parent].left = nodeMap[child]
else:
nodeMap[parent].right = nodeMap[child]
# Find the root
for key in nodeMap:
if key not in children:
return nodeMap[key]
return Noneimport java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}
class Solution {
public TreeNode createBinaryTree(int[][] descriptions) {
Map<Integer, TreeNode> nodeMap = new HashMap<>();
Set<Integer> children = new HashSet<>();
// First pass: Create all nodes
for (int[] desc : descriptions) {
nodeMap.putIfAbsent(desc[0], new TreeNode(desc[0]));
nodeMap.putIfAbsent(desc[1], new TreeNode(desc[1]));
children.add(desc[1]);
}
// Second pass: Link nodes
for (int[] desc : descriptions) {
int parent = desc[0], child = desc[1], isLeft = desc[2];
if (isLeft == 1) {
nodeMap.get(parent).left = nodeMap.get(child);
} else {
nodeMap.get(parent).right = nodeMap.get(child);
}
}
for (int key : nodeMap.keySet()) {
if (!children.contains(key)) {
return nodeMap.get(key);
}
}
return null;
}
}#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
unordered_map<int, TreeNode*> nodes;
unordered_set<int> children;
// First pass to create all tree nodes
for (const auto& desc : descriptions) {
if (nodes.find(desc[0]) == nodes.end())
nodes[desc[0]] = new TreeNode(desc[0]);
if (nodes.find(desc[1]) == nodes.end())
nodes[desc[1]] = new TreeNode(desc[1]);
children.insert(desc[1]);
}
// Second pass to link tree nodes
for (const auto& desc : descriptions) {
int parent = desc[0], child = desc[1], isLeft = desc[2];
if (isLeft) {
nodes[parent]->left = nodes[child];
} else {
nodes[parent]->right = nodes[child];
}
}
for (const auto& [key, node] : nodes) {
if (children.find(key) == children.end()) {
return node;
}
}
return nullptr;
}
};class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function createBinaryTree(descriptions) {
const nodeMap = new Map();
const children = new Set();
for (const [parent, child] of descriptions) {
if (!nodeMap.has(parent)) {
nodeMap.set(parent, new TreeNode(parent));
}
if (!nodeMap.has(child)) {
nodeMap.set(child, new TreeNode(child));
}
children.add(child);
}
for (const [parent, child, isLeft] of descriptions) {
if (isLeft === 1) {
nodeMap.get(parent).left = nodeMap.get(child);
} else {
nodeMap.get(parent).right = nodeMap.get(child);
}
}
for (const [key, node] of nodeMap) {
if (!children.has(key)) {
return node;
}
}
return null;
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
TreeNode* createBinaryTree(int** descriptions, int descriptionsSize, int* descriptionsColSize) {
TreeNode* nodes[100000] = { NULL };
bool isChild[100000] = { false };
// First pass: Create all nodes
for (int i = 0; i < descriptionsSize; ++i) {
int parentVal = descriptions[i][0], childVal = descriptions[i][1];
if (nodes[parentVal] == NULL) {
nodes[parentVal] = createNode(parentVal);
}
if (nodes[childVal] == NULL) {
nodes[childVal] = createNode(childVal);
}
isChild[childVal] = true;
}
// Second pass: Link the nodes
for (int i = 0; i < descriptionsSize; ++i) {
int parentVal = descriptions[i][0], childVal = descriptions[i][1], isLeft = descriptions[i][2];
if (isLeft) {
nodes[parentVal]->left = nodes[childVal];
} else {
nodes[parentVal]->right = nodes[childVal];
}
}
for (int i = 0; i < 100000; ++i) {
if (nodes[i] != NULL && !isChild[i]) {
return nodes[i]; // This node is not a child, hence it must be the root
}
}
return NULL;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public TreeNode CreateBinaryTree(int[][] descriptions) {
Dictionary<int, TreeNode> nodeMap = new Dictionary<int, TreeNode>();
HashSet<int> children = new HashSet<int>();
// First pass: Create all nodes
foreach (var desc in descriptions) {
int parent = desc[0], child = desc[1];
if (!nodeMap.ContainsKey(parent))
nodeMap[parent] = new TreeNode(parent);
if (!nodeMap.ContainsKey(child))
nodeMap[child] = new TreeNode(child);
children.Add(child);
}
// Second pass: Link nodes
foreach (var desc in descriptions) {
int parent = desc[0], child = desc[1], isLeft = desc[2];
if (isLeft == 1) {
nodeMap[parent].left = nodeMap[child];
} else {
nodeMap[parent].right = nodeMap[child];
}
}
foreach (var key in nodeMap.Keys) {
if (!children.Contains(key)) {
return nodeMap[key];
}
}
return null;
}
}The Python implementation separates creation and linking stages into two passes. Initial dictionary setup covers all potential nodes while recognizing child nodes, then linkage development iterates through ensuring accurate relationship formation.
Time Complexity: O(N), where N is the number of descriptions.
Space Complexity: O(V), where V is the number of unique nodes.
Approach 3: Hash Table
We can use a hash table nodes to store all nodes, where the keys are the values of the nodes, and the values are the nodes themselves. Additionally, we use a set children to store all child nodes.
We iterate through the descriptions, and for each description [parent, child, isLeft], if parent is not in nodes, we add parent to nodes and initialize a node with the value parent. If child is not in nodes, we add child to nodes and initialize a node with the value child. Then, we add child to children.
If isLeft is true, we set child as the left child of parent; otherwise, we set child as the right child of parent.
Finally, we iterate through nodes, and if a node's value is not in children, then this node is the root node, and we return this node.
The time complexity is O(n), and the space complexity is O(n), where n is the length of descriptions.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function createBinaryTree(descriptions: number[][]): TreeNode | null {
const nodes: Record<number, TreeNode> = {};
const children = new Set<number>();
for (const [parent, child, isLeft] of descriptions) {
if (!nodes[parent]) {
nodes[parent] = new TreeNode(parent);
}
if (!nodes[child]) {
nodes[child] = new TreeNode(child);
}
if (isLeft) {
nodes[parent].left = nodes[child];
} else {
nodes[parent].right = nodes[child];
}
children.add(child);
}
for (const [k, v] of Object.entries(nodes)) {
if (!children.has(+k)) {
return v;
}
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func createBinaryTree(descriptions [][]int) *TreeNode {
nodes := map[int]*TreeNode{}
children := map[int]bool{}
for _, d := range descriptions {
parent, child, isLeft := d[0], d[1], d[2]
if _, ok := nodes[parent]; !ok {
nodes[parent] = &TreeNode{Val: parent}
}
if _, ok := nodes[child]; !ok {
nodes[child] = &TreeNode{Val: child}
}
if isLeft == 1 {
nodes[parent].Left = nodes[child]
} else {
nodes[parent].Right = nodes[child]
}
children[child] = true
}
for k, v := range nodes {
if _, ok := children[k]; !ok {
return v
}
}
return nil
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::{HashMap, HashSet};
use std::rc::Rc;
impl Solution {
pub fn create_binary_tree(descriptions: Vec<Vec<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
let mut nodes = HashMap::new();
let mut children = HashSet::new();
for d in descriptions {
let parent = d[0];
let child = d[1];
let is_left = d[2];
nodes
.entry(parent)
.or_insert_with(|| Rc::new(RefCell::new(TreeNode::new(parent))));
nodes
.entry(child)
.or_insert_with(|| Rc::new(RefCell::new(TreeNode::new(child))));
if is_left == 1 {
nodes.get(&parent).unwrap().borrow_mut().left =
Some(Rc::clone(nodes.get(&child).unwrap()));
} else {
nodes.get(&parent).unwrap().borrow_mut().right =
Some(Rc::clone(nodes.get(&child).unwrap()));
}
children.insert(child);
}
for (key, node) in &nodes {
if !children.contains(key) {
return Some(Rc::clone(node));
}
}
None
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Hash Map to Track Parent-Child Relationships | Time Complexity: O(N), where N is the number of descriptions. |
| Linking Nodes Using Two-Pass Array | Time Complexity: O(N), where N is the number of descriptions. |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map to Track Parent-Child Relationships | O(n) | O(n) | Best general solution. Builds nodes and connects them in one pass with constant-time lookups. |
| Two-Pass Node Creation and Linking | O(n) | O(n) | Useful when you want clearer separation between node creation and tree construction. |
Frequently asked questions
Is Create Binary Tree From Descriptions easy or hard?
The problem is rated Medium because it requires combining tree construction with hash-based lookup. The logic itself is straightforward once you track nodes properly, but identifying the root and ensuring nodes are created only once requires careful handling.
Create Binary Tree From Descriptions Python/Java solution
Most implementations follow the same pattern across languages. Use a dictionary or HashMap to store nodes, iterate through descriptions, link children to parents, and track child nodes in a set. After processing all entries, return the node that never appears as a child as the root.
How to solve Create Binary Tree From Descriptions in O(n)?
Create a hash map that stores node values mapped to TreeNode instances. Iterate through the descriptions, create nodes if needed, and attach children to their parent using the isLeft flag. Track all child values in a set. After processing, the root is the node value that never appeared as a child.
What is the best approach for Create Binary Tree From Descriptions?
The hash map approach is the most efficient and commonly used solution. It maps node values to TreeNode objects and links parent-child relationships while iterating through the descriptions once. A set tracks which nodes appear as children, allowing you to identify the root easily. This solution runs in O(n) time with O(n) space.
Is Create Binary Tree From Descriptions asked at Google/Amazon/Meta?
Binary tree construction and parent-child relationship problems are common in interviews at companies like Amazon, Google, and Meta. This problem specifically tests your ability to map relationships efficiently using hash tables and to identify the root of a tree.
What data structure is used in Create Binary Tree From Descriptions?
The solution primarily uses a hash map to store node references and a set to track nodes that appear as children. These structures enable constant-time lookup while building the binary tree. The final output structure is a binary tree composed of TreeNode objects.
What is the time complexity of Create Binary Tree From Descriptions?
The optimal solution runs in O(n) time where n is the number of description entries. Each description is processed once, and all node lookups are constant time using a hash map. Space complexity is also O(n) because each unique node must be stored in the map.