{x}
blog image

Create Binary Tree From Descriptions

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.

2196. Create Binary Tree From Descriptions

Problem Description

Given a 2D integer array descriptions where descriptions[i] = [parent<sub>i</sub>, child<sub>i</sub>, isLeft<sub>i</sub>], construct the binary tree described and return its root. isLeft<sub>i</sub> == 1 indicates child<sub>i</sub> is the left child of parent<sub>i</sub>, otherwise it's the right child.

Solution: Hash Table Approach

This problem can be efficiently solved using a hash table (or dictionary in Python) to track nodes and their relationships. The algorithm proceeds as follows:

  1. Initialization: Create a hash table (nodes) to store nodes where keys are node values and values are TreeNode objects. Also, create a set (children) to keep track of all child nodes.

  2. Iterate through Descriptions: For each description [parent, child, isLeft] in descriptions:

    • If parent isn't in nodes, create a new TreeNode for it.
    • Do the same for child.
    • Add child to the children set.
    • Connect child to parent as either the left or right child based on isLeft.

  3. Find the Root: Iterate through the nodes hash table. The node whose value is not present in the children set is the root node (since it has no parent). Return this root node.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of descriptions. We iterate through the descriptions once to build the tree and once to find the root. All hash table operations (insertion, lookup) take roughly constant time on average.

  • Space Complexity: O(n). The hash table nodes and the set children will store at most n nodes.

Code Implementation (Python)

# 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 = {}  # Hash table to store nodes
        children = set() # Set to track children nodes
 
        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]
 
        # Find the root: the node not in children
        for node_val, node in nodes.items():
            if node_val not in children:
                return node
        return None #Should not happen given problem constraints

Code Implementation (Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.*;
class Solution {
    public TreeNode createBinaryTree(int[][] descriptions) {
        Map<Integer, TreeNode> nodes = new HashMap<>();
        Set<Integer> children = new HashSet<>();
 
        for (int[] desc : descriptions) {
            int parent = desc[0], child = desc[1], isLeft = desc[2];
            nodes.putIfAbsent(parent, new TreeNode(parent));
            nodes.putIfAbsent(child, new TreeNode(child));
            children.add(child);
            if (isLeft == 1) {
                nodes.get(parent).left = nodes.get(child);
            } else {
                nodes.get(parent).right = nodes.get(child);
            }
        }
 
        for (Map.Entry<Integer, TreeNode> entry : nodes.entrySet()) {
            if (!children.contains(entry.getKey())) {
                return entry.getValue();
            }
        }
        return null; //Should not happen given problem constraints.
    }
}

(Other language implementations would follow a similar structure, using the appropriate data structures for hash tables and sets in each language.)