Skip to main content
Talentd

Create Binary Tree From Descriptions - Solution & Explanation

MediumArrayHash TableTreeBinary Tree25 min readAsked at: Amazon, Meta, Uber +4
Practice this problem

Problem Statement

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, then childi is the left child of parenti.
  • If isLefti == 0, then childi is the right child of parenti.

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.

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.

This solution in C creates a hash map using an array to store nodes and a boolean array to track which nodes have been identified as children. It creates nodes dynamically as needed and links them based on the description inputs. It finally identifies the root by finding a node that has not been marked as a child.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N), where N is the number of descriptions.
Space Complexity: O(V), where V is the number of unique nodes.

Try this approach in the editor →

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.

This C solution divides the node creation and linking into two separate passes. It allocates the nodes in the first pass and establishes the links between them in the second pass. This approach simplifies the code logic and ensures the nodes are available when linking operations occur.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N), where N is the number of descriptions.
Space Complexity: O(V), where V is the number of unique nodes.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Hash Map to Track Parent-Child Relationships

Time Complexity: O(N), where N is the number of descriptions.
Space Complexity: O(V), where V is the number of unique nodes.

Linking Nodes Using Two-Pass Array

Time Complexity: O(N), where N is the number of descriptions.
Space Complexity: O(V), where V is the number of unique nodes.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map to Track Parent-Child RelationshipsO(n)O(n)Best general solution. Builds nodes and connects them in one pass with constant-time lookups.
Two-Pass Node Creation and LinkingO(n)O(n)Useful when you want clearer separation between node creation and tree construction.

Video Solution

Create Binary Tree From Descriptions | Simplest Approach | Leetcode 2196 | codestorywithMIK • codestorywithMIK • 14,581 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Create Binary Tree From Descriptions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Convert Sorted List to Binary Search Tree

Next

Number Of Ways To Reconstruct A Tree