Introduction

In this blog post, we will explore how to solve the LeetCode problem "2196" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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, If isLefti == 1, then childi is the left child of parenti. If 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 <= 104 descriptions[i].length == 3 1 <= parenti, childi <= 105 0 <= isLefti <= 1 The binary tree described by descriptions is valid.

Explanation

Here's the breakdown of the approach and the Python code:

• Identify the Root: Find the node that is a parent but not a child. This node will be the root of the binary tree.
• Build the Tree: Create a dictionary to store nodes by their values. Iterate through the descriptions, creating nodes and linking them based on the parent-child relationships and isLeft indicator.

• Return the Root: Return the identified root node.

• Runtime Complexity: O(N), where N is the number of descriptions. Storage Complexity: O(N)

Code

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

def create_binary_tree(descriptions):
    """
    Constructs a binary tree from a list of parent-child descriptions.

    Args:
        descriptions: A list of lists, where each inner list contains
                      [parent, child, isLeft].

    Returns:
        The root of the constructed binary tree.
    """

    node_map = {}  # Store nodes by their values
    children = set()  # Store all child node values

    for parent, child, is_left in descriptions:
        if parent not in node_map:
            node_map[parent] = TreeNode(parent)
        if child not in node_map:
            node_map[child] = TreeNode(child)

        parent_node = node_map[parent]
        child_node = node_map[child]

        if is_left == 1:
            parent_node.left = child_node
        else:
            parent_node.right = child_node

        children.add(child)

    root = None
    for parent, _, _ in descriptions:
        if parent not in children:
            root = node_map[parent]
            break

    return root