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,
isLefti == 1, then childi is the left child of parenti.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 <= 104descriptions[i].length == 31 <= parenti, childi <= 1050 <= isLefti <= 1descriptions is valid.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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), where N is the number of descriptions.
Space Complexity: O(V), where V is the number of unique nodes.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), where N is the number of descriptions.
Space Complexity: O(V), where V is the number of unique nodes.
| 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. |
Create Binary Tree from Descriptions - Leetcode 2196 - Python • NeetCodeIO • 12,034 views views
Watch 9 more video solutions →Practice Create Binary Tree From Descriptions with our built-in code editor and test cases.
Practice on FleetCode