Problem of The Day: Create Binary Tree From Descriptions
Problem Statement
Intuition
My first thought is to parse through the list of descriptions and use a dictionary to keep track of all nodes by their values. This way, I can easily access and link each node to its parent or child as specified in the descriptions. I also need to keep track of all the children to identify the root node, which will be the one node that is never a child.
Approach
- Initialize Structures: I will use a dictionary
nodesto store each node by its value. I’ll also use a setchildrento keep track of all the nodes that are children. - Process Descriptions: For each description, I’ll extract the parent, child, and whether the child is a left or right child. I’ll create nodes for the parent and child if they don’t already exist in the
nodesdictionary. - Link Nodes: Depending on whether the child is a left or right child, I’ll set the appropriate child link for the parent node.
- Identify the Root: After processing all descriptions, I’ll iterate through the keys in the
nodesdictionary to find the node that is not in thechildrenset. This node is the root. - Return the Root: Finally, I’ll return the root node of the binary tree.
Complexity
- Time Complexity: (O(n)), where (n) is the number of descriptions. Each description is processed once.
- Space Complexity: (O(n)), where (n) is the number of unique nodes. This space is used to store the nodes in the dictionary and the children in the set.
Code
# 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 = defaultdict(TreeNode)
children = set()
root = None
for desc in descriptions:
parent, child, isLeft = desc
if parent not in nodes:
nodes[parent] = TreeNode(parent)
if child not in nodes:
nodes[child] = TreeNode(child)
if isLeft:
nodes[parent].left = nodes[child]
else:
nodes[parent].right = nodes[child]
children.add(child)
for k in nodes.keys():
if k not in children:
root = nodes[k]
break
return root
Editorial
Approach 1: Convert to Graph with Breadth First Search
class Solution:
def createBinaryTree(
self, descriptions: List[List[int]]
) -> Optional[TreeNode]:
# Sets to track unique children and parents
children = set()
parents = set()
# Dictionary to store parent to children relationships
parentToChildren = {}
# Build graph from parent to child, and add nodes to sets
for d in descriptions:
parent, child, isLeft = d
parents.add(parent)
parents.add(child)
children.add(child)
if parent not in parentToChildren:
parentToChildren[parent] = []
parentToChildren[parent].append((child, isLeft))
# Find the root node by checking which node is
# in parents but not in children
for parent in parents.copy():
if parent in children:
parents.remove(parent)
root = TreeNode(next(iter(parents)))
# Starting from root, use BFS to construct binary tree
queue = deque([root])
while queue:
parent = queue.popleft()
# Iterate over children of current parent
for childValue, isLeft in parentToChildren.get(parent.val, []):
child = TreeNode(childValue)
queue.append(child)
# Attach child node to its parent based on isLeft flag
if isLeft == 1:
parent.left = child
else:
parent.right = child
return root
- time: O(n)
- space: O(n)
Approach 2: Convert to Graph with Depth First Search
class Solution:
def createBinaryTree(
self, descriptions: List[List[int]]
) -> Optional[TreeNode]:
# Step 1: Organize data
parent_to_children = {}
all_nodes = set()
children = set()
for parent, child, is_left in descriptions:
# Store child information under parent node
if parent not in parent_to_children:
parent_to_children[parent] = []
parent_to_children[parent].append((child, is_left))
all_nodes.add(parent)
all_nodes.add(child)
children.add(child)
# Step 2: Find the root
root_val = (all_nodes - children).pop()
# Step 3 & 4: Build the tree using DFS
def _dfs(val):
# Create new TreeNode for current value
node = TreeNode(val)
# If current node has children, recursively build them
if val in parent_to_children:
for child, is_left in parent_to_children[val]:
# Attach child node based on is_left flag
if is_left:
node.left = _dfs(child)
else:
node.right = _dfs(child)
return node
return _dfs(root_val)
Approach 3: Constructing Tree From Directly Map and TreeNode Object
class Solution:
def createBinaryTree(
self, descriptions: List[List[int]]
) -> Optional[TreeNode]:
# Maps values to TreeNode pointers
node_map = {}
# Stores values which are children in the descriptions
children = set()
# Iterate through description to create nodes and set up tree structure
for description in descriptions:
# Extract parent value, child value, and whether
# it is a left child (1) or right child (0)
parent_value = description[0]
child_value = description[1]
is_left = bool(description[2])
# Create parent and child nodes if not already created
if parent_value not in node_map:
node_map[parent_value] = TreeNode(parent_value)
if child_value not in node_map:
node_map[child_value] = TreeNode(child_value)
# Attach child node to parent's left or right branch
if is_left:
node_map[parent_value].left = node_map[child_value]
else:
node_map[parent_value].right = node_map[child_value]
# Mark child as a child in the set
children.add(child_value)
# Find and return the root node
for node in node_map.values():
if node.val not in children:
return node # Root node found
return None # Should not occur according to problem statement