Create Binary Tree From Descriptions

You are given a 2D integer array descriptions where descriptions[i] = [parent<sub>i</sub>, child<sub>i</sub>, isLeft<sub>i</sub>] indicates that parent<sub>i</sub> is the parent of child<sub>i</sub> in a binary tree of unique values. Furthermore: If isLeft<sub>i</sub> == 1, then child<sub>i</sub> is the left child of parent<sub>i</sub>. If isLeft<sub>i</sub> == 0, then child<sub>i</sub> is the right child of parent<sub>i</sub>. Construct the binary tree described by descriptions and return its root. The test cases will be generated such that the binary tree is valid. For example, given descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]], the root node is the node with value 50 since it has no parent. As another example, given descriptions = [[1,2,1],[2,3,0],[3,4,1]], the root node is the node with value 1 since it has no parent.

## Optimal Solution: Constructing the Binary Tree

This problem can be solved efficiently by identifying the root node and then constructing the tree using the given parent-child relationships.

### Code:

```python
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 the given descriptions."""
    child_nodes = set()
    node_map = {}

    # Create nodes and track children
    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)

        child_nodes.add(child)

        if is_left == 1:
            node_map[parent].left = node_map[child]
        else:
            node_map[parent].right = node_map[child]

    # Find the root (node that is not a child)
    root = None
    for parent, _, _ in descriptions:
        if parent not in child_nodes:
            root = node_map[parent]
            break

    return root


# Example Usage (same as provided example)
descriptions = [[20, 15, 1], [20, 17, 0], [50, 20, 1], [50, 80, 0], [80, 19, 1]]
root = create_binary_tree(descriptions)

# The function only returns the root. Here's a helper function to print out the tree in-order for your local testing:
def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val, end=" ")
        inorder_traversal(root.right)

inorder_traversal(root) # Output: 15 20 17 50 19 80

Data Structures Used:

• TreeNode: Represents a node in the binary tree with a value, left child, and right child.
• Dictionary (node_map): Stores nodes using their values as keys for quick access.
• Set (child_nodes): Keeps track of all child node values to identify the root.

Algorithm:

1. Initialization:

   • Create a TreeNode class to represent nodes in the binary tree.
   • Initialize an empty dictionary node_map to store nodes, and an empty set child_nodes to keep track of child nodes.

2. Node Creation and Child Tracking:

   • Iterate through the descriptions list.
   • For each [parent, child, is_left] entry:
     • If the parent is not in node_map, create a new TreeNode for it and add it to node_map.
     • If the child is not in node_map, create a new TreeNode for it and add it to node_map.
     • Add the child value to the child_nodes set.
     • If is_left is 1, set the child as the left child of the parent; otherwise, set it as the right child.

3. Root Identification:

   • Iterate through the descriptions list again.
   • For each [parent, _, _] entry, check if the parent is present in the child_nodes set.
   • If the parent is not in child_nodes, it means it is the root node. Retrieve the corresponding TreeNode from node_map and assign it to the root variable.
   • Break the loop once the root is found.

4. Return Root:

   • Return the root of the constructed binary tree.

Big(O) Run-time Analysis:

• Creating nodes and tracking children: O(N), where N is the number of descriptions.
• Finding the root: O(N) in the worst case.
• Total: O(N)

Big(O) Space Usage Analysis:

• node_map: O(N) to store the tree nodes.
• child_nodes: O(N) to store the child nodes.
• Total: O(N)

Edge Cases:

• Empty Input: If the descriptions list is empty, return None.
• Single Node Tree: If there's only one entry in descriptions and it represents the root with no children, the algorithm will correctly identify and return the root.
• Invalid Input: The problem states that the input will always result in a valid binary tree. If the input could be invalid (e.g., a node has two parents), additional validation logic would be needed.