medium Create Binary Tree From Descriptions

Problem Statement

You are given a 2D list called descriptions. Each element in descriptions represents a relationship in a binary tree. The element descriptions[i] = [parent_i, child_i, isLeft_i] tells us that parent_i is the paent of child_i. The isLeft_i value can be either 1 or 0:

• If isLeft_i is 1, childi is the left child of parent_i.
• If isLeft_i is 0, child_i is the right child of parent_i.

Build this binary tree from the given description and return its root node.

Each node in the binary tree has a unique value.

Examples

Example 1

• Input: descriptions = [[1, 2, 1], [1, 3, 0], [2, 4, 1]]
• Expected Output: [1, 2, 3, 4]

• Justification: Node 1 is the root, 2 is the left child, 3 is the right child. Node 2 has 4 as its left child.

Example 2:

• Input: descriptions = [[10, 5, 1], [10, 15, 0], [5, 3, 1], [15, 20, 0]]
• Expected Output: [10,5,15,3,null,null,20]

• Justification: Node 10 is the root, with 5 as the left child and 15 as the right child. Node 5 has 3 as its left child, and 15 has 20 as its right child.

Example 3:

• Input: descriptions = [[5, 3, 1], [5, 7, 0], [3, 2, 1], [3, 4, 0]]
• Expected Output: [5,3,7,2,4]

• Justification: Node 5 is the root with 3 as the left child and 7 as the right child. Node 3 has 2 as the left child and 4 as the right child.

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.

Solution

To solve this problem, we create a map to store nodes by their values. Each time we encounter a parent or child value, we ensure that a corresponding node exists in this map (by checking if the node already exists and creating it if it doesn't). We also maintain a set of child nodes to track which nodes are children in the tree. After processing the entire input, the root node will be the only node not found in this set of children (because every other node is a child of some other node). We then return this root node to represent the complete binary tree. This approach is effective because it handles all necessary tasks (node creation, tree construction, and root detection) in a single pass through the input, making it efficient.

Step-by-Step Algorithm

1. Initialize Structures:
   • Create a map (nodeMap) to store nodes using their values as keys.
   • Create a set (children) to keep track of child nodes.
2. Iterate through descriptions:
   • For each description:
     • Extract the values of parent, child, and isLeft.
     • Create or fetch parent node:
       • Check if parent exists in nodeMap. If not, create a new TreeNode for parent and put it in nodeMap.
     • Create or fetch child node:
       • Check if child exists in nodeMap. If not, create a new TreeNode for child and put it in nodeMap.
     • Add the child to the parent:
       • If isLeft == 1, set parent.left to the child.
       • If isLeft == 0, set parent.right to the child.
     • Record the child node:
       • Add the child value to the children set.
3. Determine the root:
   • Iterate through the keys (node values) in nodeMap. The node whose value is not in the children set is the root, since it is not a child of any other node.
4. Return the root node:
   • Return the node found in the previous step as the root of the binary tree.

Algorithm Walkthrough

We will now walk through the algorithm using the input:

descriptions = [[10, 5, 1], [10, 15, 0], [5, 3, 1], [15, 20, 0]]

1. Initialize nodeMap and children:

   • nodeMap = {} (empty map)
   • children = {} (empty set)

2. Processing each description:

   • First description [10, 5, 1]:
     • Parent is 10, child is 5, and isLeft == 1.
     • 10 is not in nodeMap, so we create a node for 10: TreeNode(10).
     • 5 is not in nodeMap, so we create a node for 5: TreeNode(5).
     • Set 10.left = 5.
     • Add 5 to children: children = {5}.
   • Second description [10, 15, 0]:
     • Parent is 10, child is 15, and isLeft == 0.
     • 10 is already in nodeMap, so no need to create a new node.
     • 15 is not in nodeMap, so we create a node for 15: TreeNode(15).
     • Set 10.right = 15.
     • Add 15 to children: children = {5, 15}.
   • Third description [5, 3, 1]:
     • Parent is 5, child is 3, and isLeft == 1.
     • 5 is already in nodeMap.
     • 3 is not in nodeMap, so we create a node for 3: TreeNode(3).
     • Set 5.left = 3.
     • Add 3 to children: children = {3, 5, 15}.
   • Fourth description [15, 20, 0]:
     • Parent is 15, child is 20, and isLeft == 0.
     • 15 is already in nodeMap.
     • 20 is not in nodeMap, so we create a node for 20: TreeNode(20).
     • Set 15.right = 20.
     • Add 20 to children: children = {3, 5, 15, 20}.

3. Find the root:

   • We check the keys in nodeMap: 10, 5, 15, 3, 20.
   • The value 10 is not in children, so 10 is the root.

4. Return the root:

   • The root node is TreeNode(10).

Code

import java.util.*;

// TreeNode class
// class TreeNode {
//     int val;
//     TreeNode left, right;
//     TreeNode(int val) {
//         this.val = val;
//         this.left = null;
//         this.right = null;
//     }
// }

class Solution {

  // Function to create a binary tree from descriptions
  public TreeNode createBinaryTree(int[][] descriptions) {
    Map<Integer, TreeNode> nodeMap = new HashMap<>();
    Set<Integer> children = new HashSet<>();

    // Create nodes and build tree
    for (int[] description : descriptions) {
      int parentVal = description[0];
      int childVal = description[1];
      boolean isLeft = description[2] == 1;

      // Create or get parent node
      nodeMap.putIfAbsent(parentVal, new TreeNode(parentVal));
      TreeNode parent = nodeMap.get(parentVal);

      // Create or get child node
      nodeMap.putIfAbsent(childVal, new TreeNode(childVal));
      TreeNode child = nodeMap.get(childVal);

      // Link parent to child
      if (isLeft) {
        parent.left = child;
      } else {
        parent.right = child;
      }

      children.add(childVal);
    }

    // Find root (node not present in children set)
    for (int val : nodeMap.keySet()) {
      if (!children.contains(val)) {
        return nodeMap.get(val);
      }
    }

    return null;
  }

  // Function to print the binary tree with null nodes
  public void printTree(TreeNode root) {
    if (root == null) {
      System.out.println("The tree is empty.");
      return;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    // Level-order traversal with nulls included
    while (!queue.isEmpty()) {
      int levelSize = queue.size();
      boolean levelHasNonNull = false;

      for (int i = 0; i < levelSize; i++) {
        TreeNode currentNode = queue.poll();

        // If current node is null, print "null"
        if (currentNode == null) {
          System.out.print("null ");
          queue.add(null); // Keep adding null to maintain structure
          queue.add(null);
        } else {
          System.out.print(currentNode.val + " ");
          // Add children (or null if missing)
          if (currentNode.left != null || currentNode.right != null) {
            levelHasNonNull = true;
          }
          queue.add(currentNode.left);
          queue.add(currentNode.right);
        }
      }
      System.out.println();

      // If the next level has only nulls, break the loop to avoid infinite output
      if (!levelHasNonNull) break;
    }
  }

  // Main method for testing
  public static void main(String[] args) {
    Solution solution = new Solution();
    int[][] example1 = { { 1, 2, 1 }, { 1, 3, 0 }, { 2, 4, 1 } };
    int[][] example2 = {
      { 10, 5, 1 },
      { 10, 15, 0 },
      { 5, 3, 1 },
      { 15, 20, 0 },
    };
    int[][] example3 = { { 5, 3, 1 }, { 5, 7, 0 }, { 3, 2, 1 }, { 3, 4, 0 } };

    // Test case 1
    TreeNode root1 = solution.createBinaryTree(example1);
    System.out.println("Tree 1:");
    solution.printTree(root1); // Prints the first tree

    // Test case 2
    TreeNode root2 = solution.createBinaryTree(example2);
    System.out.println("Tree 2:");
    solution.printTree(root2); // Prints the second tree

    // Test case 3
    TreeNode root3 = solution.createBinaryTree(example3);
    System.out.println("Tree 3:");
    solution.printTree(root3); // Prints the third tree
  }
}

Complexity Analysis

Time Complexity

• Tree Construction: For each description, we either create or retrieve the parent and child nodes from a hashmap, which is an operation. To traverse n descriptions, the overall time complexity is .

Therefore, the total time complexity of the solution is .

Space Complexity

• Tree Construction: We store all nodes in a hashmap and a set. The space required for this is proportional to the number of nodes, .

Thus, the space complexity of the algorithm is .