Create Binary Tree From Descriptions

Med

#2001Time: O(N), where N is the number of descriptions. The first pass iterates through all N descriptions, and the map/set operations take average O(1) time. The second pass also iterates through N descriptions. Thus, the total time is O(N + N) = O(N).Space: O(M), where M is the number of unique nodes in the tree. The `HashMap` stores a `TreeNode` for each of the M unique nodes, and the `HashSet` stores all child values (at most M-1).2 companies

Data structures

Array Hash Table Tree Binary Tree

Companies

LinkedIn Clari

Prompt

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, then child_i is the left child of parent_i.
If isLeft_i == 0, then child_i is the right child of parent_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:

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 <= 10⁴
descriptions[i].length == 3
1 <= parent_i, child_i <= 10⁵
0 <= isLeft_i <= 1
The binary tree described by descriptions is valid.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach separates the problem into two distinct phases: first, building the complete tree structure, and second, identifying the root node. It uses a HashMap to keep track of created nodes to avoid duplicates and a HashSet to record all nodes that are children. The root is then found by identifying a parent node that never appears in the set of children.

Algorithm

Initialize a HashMap<Integer, TreeNode> to map node values to TreeNode objects.
Initialize a HashSet<Integer> to store the values of all child nodes.
First Pass (Build Tree & Identify Children): Iterate through each description [parent, child, isLeft].
- For both parent and child values, if they are not already in the map, create a new TreeNode and add it to the map.
- Retrieve the parentNode and childNode from the map.
- Link them: if isLeft is 1, parentNode.left = childNode; otherwise, parentNode.right = childNode.
- Add the child value to the children set.
Second Pass (Find Root): Iterate through each description again.
- Check if the parent value from the current description exists in the children set.
- If it does not, this parent is the root.
- Return the TreeNode corresponding to this root value from the map.

Walkthrough

This approach involves two main stages. First, we construct the entire tree structure, and second, we identify the root node.

Data Structures: We use two primary data structures:
- A HashMap<Integer, TreeNode> to store each unique node. The key is the node's integer value, and the value is the TreeNode object itself. This allows for O(1) average time access to any node by its value, preventing us from creating duplicate nodes.
- A HashSet<Integer> to keep track of all values that appear as a child in any description. This set will be crucial for identifying the root later.
Pass 1: Tree Construction:
- We iterate through every description [parent, child, isLeft] in the input array.
- For each description, we ensure that both the parent and child nodes exist in our nodeMap. If a node for a given value isn't in the map, we create a new TreeNode and add it.
- We then retrieve the parentNode and childNode objects from the map.
- Based on the isLeft flag (1 for left, 0 for right), we establish the parent-child relationship: parentNode.left = childNode or parentNode.right = childNode.
- Finally, we add the child's value to our children set.
Pass 2: Root Identification:
- After the first pass, all nodes are created and linked, and we have a complete set of all child nodes. The root of the tree is the only node that is a parent but never a child.
- We can find this node by iterating through the descriptions array a second time. For each parent value, we check if it's present in our children set.
- The first parent value we encounter that is not in the children set must be the root. We then retrieve its corresponding TreeNode from the nodeMap and return it.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode createBinaryTree(int[][] descriptions) {18        Map<Integer, TreeNode> nodeMap = new HashMap<>();19        Set<Integer> children = new HashSet<>();20 21        // Pass 1: Build the tree structure and identify all children22        for (int[] desc : descriptions) {23            int parentVal = desc[0];24            int childVal = desc[1];25            boolean isLeft = desc[2] == 1;26 27            nodeMap.putIfAbsent(parentVal, new TreeNode(parentVal));28            nodeMap.putIfAbsent(childVal, new TreeNode(childVal));29 30            TreeNode parentNode = nodeMap.get(parentVal);31            TreeNode childNode = nodeMap.get(childVal);32            if (isLeft) {33                parentNode.left = childNode;34            } else {35                parentNode.right = childNode;36            }37 38            children.add(childVal);39        }40 41        // Pass 2: Find the root42        TreeNode root = null;43        for (int[] desc : descriptions) {44            int parentVal = desc[0];45            if (!children.contains(parentVal)) {46                root = nodeMap.get(parentVal);47                break; 48            }49        }50        51        return root;52    }53}

Complexity

Time

O(N), where N is the number of descriptions. The first pass iterates through all N descriptions, and the map/set operations take average O(1) time. The second pass also iterates through N descriptions. Thus, the total time is O(N + N) = O(N).

Space

O(M), where M is the number of unique nodes in the tree. The `HashMap` stores a `TreeNode` for each of the M unique nodes, and the `HashSet` stores all child values (at most M-1).

Trade-offs

Pros

Conceptually straightforward and easy to implement.
Reliably constructs the tree and finds the root by clearly separating concerns.

Cons

Requires two full passes over the input descriptions array, making it slightly less efficient than a single-pass solution.

This approach optimizes the process by building the tree and identifying all child nodes in a single pass over the input descriptions. After this pass, the nodeMap contains all the nodes and the childrenSet contains all nodes with a parent. The root is then found by identifying the single node in the map that is not in the children set.

Algorithm

Initialize a HashMap<Integer, TreeNode> called nodeMap to store created nodes.
Initialize a HashSet<Integer> called childrenSet to store the values of all child nodes.
Single Pass (Build Tree & Track Children): Iterate through each description [parentVal, childVal, isLeft].
- Get or create the parent and child nodes using nodeMap.computeIfAbsent().
- Retrieve the parentNode and childNode from nodeMap.
- Link the nodes based on isLeft.
- Add childVal to the childrenSet.
Find Root: After the loop, iterate through the keys in nodeMap.
- The first key (node value) that is not found in childrenSet is the root's value.
- Return the TreeNode associated with this root value from nodeMap.

Walkthrough

This approach improves on the two-pass method by combining tree construction and data gathering into a single, more efficient pass.

Algorithm:
1. Initialization: We start by initializing a HashMap<Integer, TreeNode> named nodeMap to map node values to their respective TreeNode objects and a HashSet<Integer> named childrenSet to record all node values that are children.
2. Single Pass: We iterate through the descriptions array just once. For each [parentVal, childVal, isLeft] entry:
  - We use nodeMap.computeIfAbsent(value, k -> new TreeNode(k)) for both parentVal and childVal. This is a concise way to get the TreeNode if it exists or create and add it to the map if it doesn't.
  - We retrieve the parentNode and childNode objects.
  - We connect them according to the isLeft flag: parentNode.left = childNode or parentNode.right = childNode.
  - We add childVal to the childrenSet.
3. Root Finding: After the loop completes, nodeMap contains all the nodes of the tree, and childrenSet contains all the nodes that have a parent. By definition, the root is the only node in the tree that does not have a parent.
4. Therefore, we can find the root by iterating through all the node values present in nodeMap.keySet(). The first value we find that is not contained in childrenSet is the value of the root node.
5. We then return the TreeNode corresponding to this root value from nodeMap. Given the problem's guarantee of a valid tree, a single unique root is guaranteed to be found.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode createBinaryTree(int[][] descriptions) {18        Map<Integer, TreeNode> nodeMap = new HashMap<>();19        Set<Integer> childrenSet = new HashSet<>();20 21        // Single pass to build the tree and populate the children set22        for (int[] description : descriptions) {23            int parentVal = description[0];24            int childVal = description[1];25            boolean isLeft = description[2] == 1;26 27            TreeNode parentNode = nodeMap.computeIfAbsent(parentVal, k -> new TreeNode(k));28            TreeNode childNode = nodeMap.computeIfAbsent(childVal, k -> new TreeNode(k));29 30            if (isLeft) {31                parentNode.left = childNode;32            } else {33                parentNode.right = childNode;34            }35            36            childrenSet.add(childVal);37        }38 39        // Find the root: the node that is never a child40        for (int nodeVal : nodeMap.keySet()) {41            if (!childrenSet.contains(nodeVal)) {42                return nodeMap.get(nodeVal);43            }44        }45 46        return null; // Should not be reached47    }48}

Complexity

Time

O(N), where N is the number of descriptions. We iterate through the `descriptions` array once (O(N)). Then, we iterate through the unique nodes in the `nodeMap` to find the root. The number of unique nodes, M, is at most 2*N. So the total time complexity is O(N + M) which simplifies to O(N).

Space

O(M), where M is the number of unique nodes. We use a `HashMap` to store M nodes and a `HashSet` to store up to M-1 child nodes. The space is proportional to the number of unique nodes.

Trade-offs

Pros

More efficient than the two-pass approach as it processes the input array only once to build the tree structure.
Maintains the same clear logic of using a map for nodes and a set for children.
Code can be made very concise using methods like computeIfAbsent.

Cons

Still requires extra space for the HashSet and a second loop (over the map's keys) to find the root after the main processing loop.

Solutions

Solution

1/** * 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; * } * } */ class Solution { public TreeNode createBinaryTree ( int [][] descriptions ) { Map < Integer , TreeNode > m = new HashMap <>(); Set < Integer > vis = new HashSet <>(); for ( int [] d : descriptions ) { int p = d [ 0 ], c = d [ 1 ], isLeft = d [ 2 ]; if (! m . containsKey ( p )) { m . put ( p , new TreeNode ( p )); } if (! m . containsKey ( c )) { m . put ( c , new TreeNode ( c )); } if ( isLeft == 1 ) { m . get ( p ). left = m . get ( c ); } else { m . get ( p ). right = m . get ( c ); } vis . add ( c ); } for ( Map . Entry < Integer , TreeNode > entry : m . entrySet ()) { if (! vis . contains ( entry . getKey ())) { return entry . getValue (); } } return null ; } }

1/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {number[][]} descriptions * @return {TreeNode} */ var createBinaryTree =2  function (descriptions) {3    const nodes = {};4    const children = new Set();5    for (const [parent, child, isLeft] of descriptions) {6      if (!nodes[parent]) {7        nodes[parent] = new TreeNode(parent);8      }9      if (!nodes[child]) {10        nodes[child] = new TreeNode(child);11      }12      if (isLeft) {13        nodes[parent].left = nodes[child];14      } else {15        nodes[parent].right = nodes[child];16      }17      children.add(child);18    }19    for (const [k, v] of Object.entries(nodes)) {20      if (!children.has(+k)) {21        return v;22      }23    }24  };

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * createBinaryTree ( vector < vector < int >>& descriptions ) { unordered_map < int , TreeNode *> m ; unordered_set < int > vis ; for ( auto & d : descriptions ) { int p = d [ 0 ], c = d [ 1 ], left = d [ 2 ]; if ( ! m . count ( p )) m [ p ] = new TreeNode ( p ); if ( ! m . count ( c )) m [ c ] = new TreeNode ( c ); if ( left ) m [ p ] -> left = m [ c ]; else m [ p ] -> right = m [ c ]; vis . insert ( c ); } for ( auto & [ v , node ] : m ) { if ( ! vis . count ( v )) return node ; } return nullptr ; } };

1# 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 ]: g = defaultdict ( TreeNode ) vis = set () for p , c , left in descriptions : if p not in g : g [ p ] = TreeNode ( p ) if c not in g : g [ c ] = TreeNode ( c ) if left : g [ p ]. left = g [ c ] else : g [ p ]. right = g [ c ] vis . add ( c ) for v , node in g . items (): if v not in vis : return node

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem