Create Binary Tree From Descriptions

Problem Statement

In this task, you are given an array, descriptions, each element of which is another array detailing the parent-child relationship in a binary tree. Each sub-array in descriptions has three elements:

• the first element is the parent node value,
• the second element is the child node value,
• the third element is a flag (either 0 or 1) which determines if the child node is a left child (1) or a right child (0) of the given parent node.

Your goal is to construct the binary tree described by these arrays. Specifically, you need to build up this tree from the relations described and return the root of this binary tree. The constraints ensure that the input will always describe a valid binary tree, meaning every node will correctly follow the binary tree structure, there are no duplicate nodes in the descriptions, and every node except the root has exactly one parent.

Examples

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 <= 104
• descriptions[i].length == 3
• 1 <= parenti, childi <= 105
• 0 <= isLefti <= 1
• The binary tree described by descriptions is valid.

Approach and Intuition

To construct the binary tree from the given description, follow these steps:

1. Initialize a dictionary to store the node reference against its value for direct access to any node given its value.
2. Create another set to record all child nodes. This set helps in determining the root of the binary tree, as the root will not appear as a child in any of the descriptions.
3. Iterate over the descriptions array. For each description:
   • Check if the parent node already exists in the dictionary; if not, create a new node and add it to the dictionary.
   • Similarly, check for the existence of the child node and create it if necessary.
   • Depending on the value of isLefti, assign the child node to the left or right of the parent node.
4. After structuring all nodes, identify the root node. The root can be found as the node that never appears as a child in any input pairing. This can be determined using the set where we stored child nodes.
5. Return the reference to the root node.

This approach efficiently structures the tree in a single pass through the descriptions array followed by a simple search in a set, making the approach both straightforward and efficient given the constraints.

Solutions

class Solution {
public:
    TreeNode* constructBinaryTree(vector<vector<int>>& data) {
        unordered_map<int, TreeNode*> nodes;
        unordered_set<int> childNodes;
    
        for (const auto& item : data) {
            int parent = item[0];
            int child = item[1];
            bool isLeftChild = item[2] == 1;
    
            if (nodes.find(parent) == nodes.end()) {
                nodes[parent] = new TreeNode(parent);
            }
            if (nodes.find(child) == nodes.end()) {
                nodes[child] = new TreeNode(child);
            }
    
            if (isLeftChild) {
                nodes[parent]->left = nodes[child];
            } else {
                nodes[parent]->right = nodes[child];
            }
    
            childNodes.insert(child);
        }
    
        for (const auto& node : nodes) {
            if (childNodes.find(node.first) == childNodes.end()) {
                return node.second;
            }
        }
    
        return nullptr;
    }
};