Create Binary Tree From Descriptions

Problem

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.

Examples

Example 1:

       50
    /      \
  20        80
 /  \      /
15   17   19

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:

   1
  /
 2
  \
    3
   /
  4

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.

Solution

Method 1 - Two Pass using HashMap

Here is a step-by-step approach:

1. Use a map to create nodes and store parent-child relationships.
2. Use a set to store the list of children, this helps keep track of all child nodes to easily identify the root node.

Now, in first pass

1. Go through all descriptions add update parent-child map and children set
2. In second pass, see which is the root node, by checking the children set. If the description parent is not present, that is the root node.
3. Finally, return the root node.

Here is the video explanation: <div class="youtube-embed"><iframe src="https://www.youtube.com/embed/xP_poGETino" frameborder="0" allowfullscreen></iframe></div>

Code

Java

public class Solution {

	public TreeNode createBinaryTree(int[][] descriptions) {
		Map<Integer, TreeNode> map = new HashMap<>();
		Set<Integer> children = new HashSet<>();

		// Process each description and build the nodes and relationship
		for (int[] desc: descriptions) {
			int parent = desc[0];
			int child = desc[1];
			boolean isLeft = desc[2] == 1;

			map.putIfAbsent(parent, new TreeNode(parent));
			map.putIfAbsent(child, new TreeNode(child));

			if (isLeft) {
				map.get(parent).left = map.get(child);
			} else {
				map.get(parent).right = map.get(child);
			}

			children.add(child);
		}

		// The root will be the only node that is not a child of any other node
		TreeNode root = null;

		for (int[] desc: descriptions) {
			if (!children.contains(desc[0])) {
				root = map.get(desc[0]);
				break;
			}
		}

		return root;
	}
}

Complexity

• ⏰ Time complexity: O(n), where n is number of descriptions
• 🧺 Space complexity: O(m), where m is number of unique nodes in tree, but in worst case it is equal to n.