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.

Description Hints 3 Solution Video 19:14

2196. Create Binary Tree From Descriptions

Medium83.9% acceptance7 companies

You are given a 2D integer array descriptions where descriptions[i] = [parent_i, child_i, isLeft_i] indicates that parent_i is the parent of child_i in a binary tree of unique values. Furthermore,

If isLeft_i == 1, then child_i is the left child of parent_i.
If isLeft_i == 0, then child_i is the right child of parent_i.

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 <= 10⁴
descriptions[i].length == 3
1 <= parent_i, child_i <= 10⁵
0 <= isLeft_i <= 1
The binary tree described by descriptions is valid.

Asked at 7 companies

Clari Amazon Uber LinkedIn Bloomberg

Google Meta

Topics

Hints open one at a time

Hint 1

Could you represent and store the descriptions more efficiently?

Hint 2

Could you find the root node?

Hint 3

The node that is not a child in any of the descriptions is the root node.

19:14

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution