LeetCode 2196 - Create Binary Tree From Descriptions

The problem asks us to construct a binary tree from a list of relationships, where each relationship is given as [parent, child, isLeft].

leetcodemediumarrayhash-tabletreebinary-tree

LeetCode Problem 2196

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Tree, Binary Tree

Solution

Problem Understanding

The problem asks us to construct a binary tree from a list of relationships, where each relationship is given as [parent, child, isLeft]. Here, parent is the value of a node, child is the value of its direct descendant, and isLeft indicates whether child is a left child (1) or a right child (0). All node values are unique, so each value corresponds to exactly one tree node.

The input is a 2D array of size up to 10,000, and values can be as large as 100,000. This tells us that the solution needs to be efficient in both time and space, as a naive O(n²) search to find parents or children could be too slow.

The output is the root node of the tree, which is defined as the node that does not appear as a child in any description. The problem guarantees that the binary tree is valid, meaning there are no cycles and each child has exactly one parent.

Important edge cases include the tree being essentially a linked list (all nodes either left or right), or the smallest possible input where there is only one parent-child pair.

Approaches

A brute-force approach would create tree nodes on demand and, for each description, search through existing nodes to attach the child to the correct parent. This approach is correct but inefficient because searching for nodes repeatedly could lead to O(n²) complexity.

The optimal approach leverages hash maps to efficiently store and retrieve nodes and to determine the root. We can create all nodes in one pass using a value → TreeNode map and another set to keep track of children. The node that never appears as a child is the root. This avoids repeated searches and allows us to attach children in O(1) time per description.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly searches for parent nodes in a growing list of nodes
Optimal O(n) O(n) Uses hash maps to track nodes and children efficiently

Algorithm Walkthrough

  1. Initialize an empty dictionary nodes to map values to TreeNode objects. This allows instant retrieval or creation of nodes by value.
  2. Initialize an empty set children to keep track of all node values that appear as a child. This will help us identify the root later.
  3. Iterate through each description [parent, child, isLeft]. For each value, check if it exists in nodes. If not, create a new TreeNode and add it to nodes.
  4. Update the children set by adding child.
  5. Attach the child node to the parent node as a left child if isLeft == 1 or as a right child if isLeft == 0.
  6. After processing all descriptions, the root is the node whose value is in nodes but not in children. Retrieve and return this node.

Why it works: Each node is created exactly once and attached according to the descriptions. Since the problem guarantees a valid tree, there will be exactly one node that is not a child, ensuring a unique root. Using hash maps ensures that node retrieval is O(1), giving an overall linear solution.

Python Solution

# 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]]) -> TreeNode:
        nodes = {}
        children = set()
        
        for parent_val, child_val, is_left in descriptions:
            if parent_val not in nodes:
                nodes[parent_val] = TreeNode(parent_val)
            if child_val not in nodes:
                nodes[child_val] = TreeNode(child_val)
            
            children.add(child_val)
            
            if is_left:
                nodes[parent_val].left = nodes[child_val]
            else:
                nodes[parent_val].right = nodes[child_val]
        
        for val in nodes:
            if val not in children:
                return nodes[val]

The Python implementation uses a dictionary to store nodes and a set to track children. Each description is processed once, creating nodes as needed and linking them based on the isLeft flag. Finally, we iterate over the node values to find the one not in the children set, which is the root.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func createBinaryTree(descriptions [][]int) *TreeNode {
    nodes := make(map[int]*TreeNode)
    children := make(map[int]bool)
    
    for _, desc := range descriptions {
        parentVal, childVal, isLeft := desc[0], desc[1], desc[2]
        
        if _, ok := nodes[parentVal]; !ok {
            nodes[parentVal] = &TreeNode{Val: parentVal}
        }
        if _, ok := nodes[childVal]; !ok {
            nodes[childVal] = &TreeNode{Val: childVal}
        }
        
        children[childVal] = true
        
        if isLeft == 1 {
            nodes[parentVal].Left = nodes[childVal]
        } else {
            nodes[parentVal].Right = nodes[childVal]
        }
    }
    
    for val, node := range nodes {
        if !children[val] {
            return node
        }
    }
    return nil
}

The Go implementation mirrors the Python solution but uses a map[int]*TreeNode for nodes and map[int]bool for tracking children. The logic for attaching children and identifying the root is identical, with nil handling implicit when returning the root if not found.

Worked Examples

Example 1: [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]

Step Nodes Map Children Set Operation
1 {20, 15} {15} Add left child 15 to 20
2 {20, 15, 17} {15,17} Add right child 17 to 20
3 {20,15,17,50} {15,17,20} Add left child 20 to 50
4 {20,15,17,50,80} {15,17,20,80} Add right child 80 to 50
5 {20,15,17,50,80,19} {15,17,20,80,19} Add left child 19 to 80
Final Root is 50 (not in children set) Return node 50

Example 2: [[1,2,1],[2,3,0],[3,4,1]]

Step Nodes Map Children Set Operation
1 {1,2} {2} Add left child 2 to 1
2 {1,2,3} {2,3} Add right child 3 to 2
3 {1,2,3,4} {2,3,4} Add left child 4 to 3
Final Root is 1 (not in children set) Return node 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate over each description once and perform O(1) operations per description using hash maps
Space O(n) We store all nodes in a map and track all children in a set, both of size O(n)

The algorithm is linear because every description is processed exactly once, and hash map lookups and insertions are O(1).

Test Cases

# test cases
sol = Solution()

# Example 1
assert sol.createBinaryTree([[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]).val == 50

# Example 2
assert sol.createBinaryTree([[1,2,1],[2,3,0],[3,4,1]]).val == 1

# Single pair
assert sol.createBinaryTree([[10,5,1]]).val == 10

# Left-skewed tree
assert sol.createBinaryTree([[1,2,1],[2,3,1],[3,4,1]]).val == 1

# Right-skewed tree
assert sol.createBinaryTree([[1,2,0],[2,3,0],[3,4,0]]).val == 1

# Mixed tree
assert sol.createBinaryTree([[5,3,1],[5,8,0],[3,2,1],[3,4,0],[8,7,1]]).val == 5
Test Why
Example 1 Validates complex tree with multiple branches
Example 2 Validates linear chain structure
Single pair Edge case with minimal input
Left-skewed tree Tests all left children