Create Binary Tree From Descriptions

Leetcode Problem:

• Create Binary Tree From Descriptions

Summary

• Constructing a binary tree from given descriptions of parent-child relationships.

Approach

• We use a map to store the nodes of the binary tree, where the key is the node value and the value is a pointer to the node
• We also use another map to store the parent of each node
• We iterate through the descriptions and create the nodes and their children accordingly
• Finally, we find the root of the tree by following the parent map until we reach a node that has no parent.

Complexity

• O(n), where n is the number of descriptions, because we make a single pass through the descriptions to create the nodes and their children.

Explain

• The solution starts by creating two maps: `myMap` to store the nodes and `parentMap` to store the parent of each node
• We then iterate through the descriptions and create the nodes and their children accordingly
• If a node does not exist in `myMap`, we create it
• We then set the left or right child of the parent node based on the value of `isLeft`
• Finally, we find the root of the tree by following the parent map until we reach a node that has no parent
• The time complexity is O(n) because we make a single pass through the descriptions to create the nodes and their children.

Solution Code:

/**
 * 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>& descriptions) {
        map myMap;
        map parentMap;
        int root = descriptions[0][0];
        for(int i = 0 ; i < descriptions.size(); i++){
            int parent = descriptions[i][0];
            int child = descriptions[i][1];
            int isLeft = descriptions[i][2];
            parentMap[child] = parent;
            if (myMap.find(parent) == myMap.end()){
                myMap[parent] = new TreeNode(parent);
            }
            if (myMap.find(child) == myMap.end()){
                myMap[child] = new TreeNode(child);
            }
            if (isLeft == 1){
                myMap[parent]->left = myMap[child];
            } else {
                myMap[parent]->right = myMap[child];
            }
        }
        while(parentMap.find(root) != parentMap.end()){
            root = parentMap[root];
        }
        return myMap[root];
    }
};