We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Create Binary Tree From Descriptions

Number: 2306

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Uber, LinkedIn, Clari

Problem Description

Given a list of descriptions, where each description is an array [parent, child, isLeft] representing that the parent node has a child node, determine whether that child is a left child (if isLeft is 1) or a right child (if isLeft is 0). The tree is guaranteed to be valid and all nodes have distinct values. The goal is to construct the binary tree and return its root.

Key Insights

  • Each description provides a parent-child relationship information.
  • The tree nodes are unique; therefore, we can use a hash table (or map) to record node values to node instances.
  • The root node is the only node that never appears as a child in any description.
  • By iterating over the descriptions, we can construct the tree by attaching each child to its corresponding parent's left or right pointer as indicated by isLeft.

Space and Time Complexity

Time Complexity: O(n) where n is the number of descriptions, since we process each description once. Space Complexity: O(n) for storing the mapping of node values to nodes and the set of child nodes.

Solution

We use a hash table (or dictionary/map) to store nodes, ensuring that each node is created only once. Another set is used to keep track of all nodes that appear as a child. After processing every description, the root of the tree will be the node that does not appear in the child set. This approach ensures an efficient, one-pass solution to constructing the tree.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val):
        # Initialize node value and left/right child pointers
        self.val = val
        self.left = None
        self.right = None

def createBinaryTree(descriptions):
    # Dictionary to map node values to TreeNode instances
    nodes = {}
    # Set to track all nodes that are children
    children = set()
    
    # Process each description to build parent-child relationships
    for parent, child, isLeft in descriptions:
        # Create parent node if it doesn't exist
        if parent not in nodes:
            nodes[parent] = TreeNode(parent)
        # Create child node if it doesn't exist
        if child not in nodes:
            nodes[child] = TreeNode(child)
        # Set left or right pointer based on isLeft flag
        if isLeft == 1:
            nodes[parent].left = nodes[child]
        else:
            nodes[parent].right = nodes[child]
        # Mark this node as having a parent
        children.add(child)
    
    # The root is the node that never appeared as a child
    for node_val in nodes:
        if node_val not in children:
            return nodes[node_val]
    return None
← Back to All Questions