#2196

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Create Binary Tree From Descriptions

Build a binary tree from descriptions of parent-child relationships using array scanning and hash lookup.

Problem Statement

You are given a 2D integer array, descriptions, where each element represents a parent-child relationship in a binary tree. The structure descriptions[i] = [parenti, childi, isLefti] tells you that parenti is the parent of childi, and isLefti indicates whether childi is the left child (isLefti = 1) or the right child (isLefti = 0).

Your goal is to reconstruct the binary tree from these relationships and return the root node of the tree. Note that the test cases will always guarantee the validity of the tree, with each parent having a unique child assignment.

Examples

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]

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]

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 Approach

Use a Hash Map for Fast Access

Store each parent node in a hash map, mapping parent values to their corresponding TreeNode. This allows quick lookups to check if a node already exists and to attach the child node efficiently.

Identify the Root Node

The root of the tree is the node that never appears as a child. Iterate over the descriptions, keeping track of all child nodes and identifying the one node not in the set of children as the root.

Reconstruct the Binary Tree

Iterate through the descriptions again to set the left and right children of the parent nodes. Use the isLeft flag to determine whether to assign the child as the left or right child.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity of this solution is O(n), where n is the number of descriptions, as we process each description once. The space complexity is O(n) due to the storage of nodes in the hash map and potentially for the binary tree itself.

What Interviewers Usually Probe

Can the candidate handle efficient tree construction using hash maps?
Does the candidate identify the root node correctly without extra checks?
How well does the candidate optimize space and time complexity while solving the problem?

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the identification of the root node, which should be straightforward by excluding children.
Not utilizing hash maps effectively, which can lead to inefficient lookups when constructing the tree.
Confusing left and right child assignments, especially if the index or flag is misinterpreted.

Follow-up variants

What if the tree had additional constraints, such as balanced or full binary trees?
How would the solution change if the parent-child descriptions were in a different format?
How can we optimize the space complexity if we were asked to process multiple trees simultaneously?

FAQ

What is the primary approach for solving the Create Binary Tree From Descriptions problem?

The problem can be efficiently solved using array scanning and hash lookup to quickly identify parent-child relationships and reconstruct the tree.

How do I find the root node in the Create Binary Tree From Descriptions problem?

The root node is the one that does not appear as a child in any description. Track all child nodes and the missing one will be the root.

What is the time complexity of the solution for Create Binary Tree From Descriptions?

The time complexity is O(n), where n is the number of descriptions, as we process each description once to build the tree.

What is the space complexity of the Create Binary Tree From Descriptions solution?

The space complexity is O(n) because we store the nodes in a hash map and potentially in the resulting tree structure.

What should I focus on when solving the Create Binary Tree From Descriptions problem?

Focus on efficiently constructing the tree using hash lookups, correctly assigning children, and identifying the root node without excessive checks.

terminal

Solution

Solution 1: Hash Table

We can use a hash table $\textit{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 $\textit{children}$ to store all child nodes.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# 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]:
        nodes = defaultdict(TreeNode)
        children = set()
        for parent, child, isLeft in descriptions:
            if parent not in nodes:
                nodes[parent] = TreeNode(parent)
            if child not in nodes:
                nodes[child] = TreeNode(child)
            children.add(child)
            if isLeft:
                nodes[parent].left = nodes[child]
            else:
                nodes[parent].right = nodes[child]
        root = (set(nodes.keys()) - children).pop()
        return nodes[root]

Continue Practicing

#1110 delete nodes and return forest #2049 count nodes with the highest score #2368 reachable nodes with restrictions