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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Create Binary Tree From Descriptions

Difficulty: Medium

Problem Description

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. 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.

Key Insights

  • Each entry in the descriptions array provides a relationship between a parent and a child.
  • A parent node can have at most two children (left and right).
  • The root node is the only node that does not appear as a child in any entry, making it identifiable through the relationships.
  • A hash table (or dictionary) can be used to track nodes and their children efficiently.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of descriptions since each relationship is processed once. Space Complexity: O(n) - for storing nodes and their children in a hash table.

Solution

We will use a hash table to store the nodes and their corresponding children. As we iterate through the descriptions, we will create nodes and link them according to the specified parent-child relationships. Finally, we will identify the root node by tracking which nodes do not have parents.

Code Solutions

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def createBinaryTree(descriptions):
    nodes = {}
    has_parent = 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)

        has_parent.add(child)

        if isLeft:
            nodes[parent].left = nodes[child]
        else:
            nodes[parent].right = nodes[child]

    # The root is the only node that is not a child of any node
    for node in nodes:
        if node not in has_parent:
            return nodes[node]
← Back to All Questions