Create Binary Tree From Descriptions
Medium
You are given a 2D integer array descriptions where descriptions[i] = [parent_i, child_i, isLeft_i] indicates that parent_i is the parent of child_i in a binary tree of unique values. Furthermore:
- If
isLeft_i == 1, thenchild_iis the left child ofparent_i. - If
isLeft_i == 0, thenchild_iis the right child ofparent_i.
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:
descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
In this example, the root node is the node with value 50 since it has no parent. The resulting binary tree would look like this:
50
/ \
20 80
/ \ \
15 17 19
Example 2:
descriptions = [[1,2,1],[2,3,0],[3,4,1]]
In this case, the root node is the node with value 1 since it has no parent. The resulting binary tree would be:
1
/
2
\
3
/
4
Could you provide a function that takes the descriptions array as input and returns the root of the constructed binary tree? Consider the efficiency of your solution in terms of both time and space complexity. Also, what edge cases should be taken into account?
Solution
Let's walk through how to solve the problem of constructing a binary tree from its descriptions, and identifying the root node.
Naive Approach
A brute force approach involves iterating through the descriptions array and building the tree node by node. We keep track of all nodes created. Then, we iterate through the descriptions again to establish the parent-child relationships. Finally, to find the root, we check which node doesn't have a parent.
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_naive(descriptions):
node_map = {}
children = set()
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)
children.add(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
root = None
for node_val, node in node_map.items():
if node_val not in children:
root = node
break
return root
Time Complexity: O(N), where N is the number of descriptions. We iterate through the descriptions twice and the node map once.
Space Complexity: O(N), to store the nodes in the node_map dictionary.
Optimal Approach
To optimize, we can track the children nodes in a set as we build the tree. After processing all descriptions, the root is the node that is not in the children set. This avoids the extra iteration in the naive approach.
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):
node_map = {}
children = set()
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)
children.add(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
root = None
for node_val, node in node_map.items():
if node_val not in children:
root = node
break
return root
Time Complexity: O(N), where N is the number of descriptions. We iterate through the descriptions once to build the tree and once to find the root.
Space Complexity: O(N), to store the nodes in the node_map dictionary and the children in the children set.
Edge Cases
- Empty Input: If the input
descriptionsis empty, the tree is empty, and we should returnNone. - Single Node Tree: If there is only one description, both parent and child nodes should be created accordingly.
- Multiple potential Roots: The problem statement guarantees a valid binary tree, so this situation cannot happen.
Summary
The optimal approach provides a clean and efficient way to construct the binary tree and find its root in O(N) time complexity. It leverages a set to track children, avoiding unnecessary iterations. Edge cases are minimal due to the problem constraints, but it's always good to consider them.
