2196. Create Binary Tree From Descriptions

MediumTreeDepth-First SearchBreadth-First SearchArrayHash TableBinary Tree
Leetcode Link

Problem Description

In this problem, you are given a 2D integer array named descriptions. Each element of descriptions is a triple [parent_i, child_i, isLeft_i] where:

  • parent_i is the value of a parent node in a binary tree.
  • child_i is the value of the child node associated with parent_i.
  • isLeft_i determines the position of the child_i with respect to parent_i. A value of 1 means child_i is the left child of parent_i, while a value of 0 means child_i is the right child.

Your task is to build the binary tree described by descriptions and return the root node of that binary tree. It's guaranteed that the input descriptions will describe a valid binary tree where each value is unique.

Intuition

The intuition behind solving this problem involves understanding how a binary tree is structured and how the information given in descriptions can be used to construct such a tree. We need to keep track of the nodes and their relationships.

The solution involves two main steps:

  1. Create all nodes and store them in a dictionary with their values as keys, so that any node can be accessed instantly when needed.
  2. Set up parent-child relationships according to the descriptions. As we connect children to their parents, we also keep track of which nodes have been assigned as children. This is done because the root of the tree will never be assigned as a child.

Finally, after all descriptions are processed, we find the node that has not been assigned as a child. This node will be the root of our binary tree, and hence, is returned as the result.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Solution Approach

The implementation of the solution follows these steps:

  • First, we use a dictionary g to map the value of each node to the corresponding TreeNode object. We use the defaultdict from the collections module in Python which helps to automatically create a new TreeNode if the value is not already in the dictionary. This is helpful for quickly accessing and storing nodes by their values.

  • As we iterate through each description (parent_i, child_i, isLeft_i), we need to check if the parent and child nodes already exist in the dictionary g. If they do not, we create them and store them. This ensures that all nodes are created before we start setting up relationships.

  • Then, based on the isLeft_i value, we link the parent node to the child node by setting either the left or right pointer of the parent's TreeNode object to the child's TreeNode object. This sets up the left and right child relationships as described by the input.

  • While setting up these relationships, we also keep a vis set which keeps track of all the nodes that have been assigned as a child to some parent node. This set is crucial for identifying the root node later because the root will not be a child of any node.

  • Finally, once all descriptions are processed, we iterate through the nodes in the dictionary g. For each node, we check if it is not present in the vis set. The node not present in vis is the one which has never been assigned as a child, indicating it's the root of the tree. We return this root node.

In terms of data structures, this solution uses:

  • A defaultdict to construct the nodes dynamically and access them efficiently.
  • A set to keep track of all child nodes encountered.
  • The binary tree nodes are represented by instances of a class TreeNode, where each node stores a value and two pointers, one for its left child and one for its right child.

This approach follows a pattern often used in tree construction problems, where relationships between nodes are established based on given pairs or tuples and a data structure is required to instantly access any node based on a unique identifier (in this case, the node's value).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the following descriptions array:

1descriptions = [[20, 15, 1], [20, 17, 0], [50, 20, 1], [50, 80, 0], [80, 19, 1]]

This input describes a binary tree with the following structure:

1       50
2      /  \
3    20    80
4   / \    /
5 15  17  19

Step by step, we follow the instructions:

  1. We initialize a default dictionary g and a set vis as follows:

    • g = defaultdict(TreeNode) which will hold the nodes.
    • vis = set() which will keep track of all child nodes.

  2. As we iterate through the descriptions:

    For the first triple [20, 15, 1]:

    • Create nodes for 20 and 15 if they don't exist in g.
    • Since isLeft_i is 1, link 20's left child to 15.
    • Add 15 to the vis set as it is now a known child node.

    For the second triple [20, 17, 0]:

    • Create nodes for 20 and 17 if they don't exist in g.
    • Link 20's right child to 17 because isLeft_i is 0.
    • Add 17 to the vis set.

    For the third triple [50, 20, 1]:

    • Create a node for 50 (20 is already created).
    • Link 50's left child to 20.
    • Add 20 to the vis set.

    For the fourth triple [50, 80, 0]:

    • Create a node for 80.
    • Link 50's right child to 80.
    • Add 80 to the vis set.

    For the last triple [80, 19, 1]:

    • Create a node for 19.
    • Link 80's left child to 19.
    • Add 19 to the vis set.

  3. After processing all descriptions, we find the root node:

    • Iterate through g and find a node that is not in the vis set. In this case, it is the node with value 50 because it's the only node that was not added to vis as it was never assigned as a child. Hence, 50 is the root of the tree.

  4. Return the root node (The node with value 50), which points to the complete tree structure as described.

Solution Implementation

1from typing import List, Optional
2from collections import defaultdict
3
4# Definition for a binary tree node.
5class TreeNode:
6    def __init__(self, val=0, left=None, right=None):
7        self.val = val
8        self.left = left
9        self.right = right
10
11class Solution:
12    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
13        # Initialize a map to store TreeNode objects with integer identifiers as keys
14        nodes_map = defaultdict(TreeNode)
15      
16        # Initialize a set to keep track of child nodes
17        children_set = set()
18      
19        # Iterate over the descriptions list and build the tree
20        for parent_val, child_val, is_left in descriptions:
21            # Create the parent node if it doesn't exist in the nodes map
22            if parent_val not in nodes_map:
23                nodes_map[parent_val] = TreeNode(parent_val)
24          
25            # Create the child node if it doesn't exist in the nodes map
26            if child_val not in nodes_map:
27                nodes_map[child_val] = TreeNode(child_val)
28          
29            # Link the child node to the left or right of the parent based on the flag 'is_left'
30            if is_left:
31                nodes_map[parent_val].left = nodes_map[child_val]
32            else:
33                nodes_map[parent_val].right = nodes_map[child_val]
34          
35            # Add the child_val to the set of child nodes
36            children_set.add(child_val)
37      
38        # The root node will be the one that is never referenced as a child
39        # Find this node and return it as the root of the constructed binary tree
40        for value, node in nodes_map.items():
41            if value not in children_set:
42                return node
43        return None  # In case the tree cannot be constructed, return None
44
1import java.util.HashMap;
2import java.util.HashSet;
3import java.util.Map;
4import java.util.Set;
5
6/**
7 * Definition for a binary tree node.
8 */
9class TreeNode {
10    int val;
11    TreeNode left;
12    TreeNode right;
13
14    TreeNode() {}
15
16    TreeNode(int val) {
17        this.val = val;
18    }
19
20    TreeNode(int val, TreeNode left, TreeNode right) {
21        this.val = val;
22        this.left = left;
23        this.right = right;
24    }
25}
26
27class Solution {
28    /**
29     * Creates a binary tree from a list of node descriptions.
30     *
31     * @param descriptions Array of triples describing the tree. Each triple contains the parent value,
32     *                     child value, and a flag to indicate if the child is a left or right child.
33     * @return The root of the constructed binary tree.
34     */
35    public TreeNode createBinaryTree(int[][] descriptions) {
36        // Map to store the value and corresponding TreeNode
37        Map<Integer, TreeNode> nodeMap = new HashMap<>();
38      
39        // Set to track visited child nodes
40        Set<Integer> visited = new HashSet<>();
41
42        // Loop through each description to build the tree
43        for (int[] description : descriptions) {
44            int parentValue = description[0];
45            int childValue = description[1];
46            int isLeftChild = description[2];
47
48			// Ensure that a TreeNode exists for the parentValue
49            if (!nodeMap.containsKey(parentValue)) {
50                nodeMap.put(parentValue, new TreeNode(parentValue));
51            }
52
53            // Ensure that a TreeNode exists for the childValue
54            if (!nodeMap.containsKey(childValue)) {
55                nodeMap.put(childValue, new TreeNode(childValue));
56            }
57
58            // Link parent to child appropriately based on isLeftChild flag
59            if (isLeftChild == 1) {
60                nodeMap.get(parentValue).left = nodeMap.get(childValue);
61            } else {
62                nodeMap.get(parentValue).right = nodeMap.get(childValue);
63            }
64
65            // Mark the child as visited
66            visited.add(childValue);
67        }
68
69        // Find the root of the binary tree (the node that was never visited as a child)
70        for (Map.Entry<Integer, TreeNode> entry : nodeMap.entrySet()) {
71            if (!visited.contains(entry.getKey())) {
72                return entry.getValue();
73            }
74        }
75
76        // In case no root is found (which shouldn't happen if input is valid), return null
77        return null;
78    }
79}
80
1#include <unordered_map>
2#include <unordered_set>
3#include <vector>
4
5// Definition for a binary tree node.
6struct TreeNode {
7    int val;
8    TreeNode *left;
9    TreeNode *right;
10    // Constructor to initialize the node with a value, left and right children set to nullptr by default
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12    // Constructor to initialize the node with a value and explicit left and right children
13    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
14};
15
16class Solution {
17public:
18    // Creates a binary tree based on a list of descriptions and returns the root of the tree
19    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
20        unordered_map<int, TreeNode*> nodeMap; // Maps values to TreeNode pointers
21        unordered_set<int> children; // Stores values which are children in the descriptions
22
23        // Iterate through each description to create the nodes and set up the tree structure
24        for (const auto& description : descriptions) {
25            // Extract parent value, child value, and whether it is a left child (1) or right child (0)
26            int parentValue = description[0];
27            int childValue = description[1];
28            bool isLeft = description[2];
29
30            // If the parent node is not already created, create it and add to the map
31            if (nodeMap.count(parentValue) == 0) {
32                nodeMap[parentValue] = new TreeNode(parentValue);
33            }
34
35            // If the child node is not already created, create it and add to the map
36            if (nodeMap.count(childValue) == 0) {
37                nodeMap[childValue] = new TreeNode(childValue);
38            }
39
40            // Attach the child node to the left or right branch of the parent node
41            if (isLeft) {
42                nodeMap[parentValue]->left = nodeMap[childValue];
43            } else {
44                nodeMap[parentValue]->right = nodeMap[childValue];
45            }
46
47            // Mark the child value as being a child in the set
48            children.insert(childValue);
49        }
50
51        // Find the root of the tree (a node which is not marked as a child)
52        for (const auto& [value, node] : nodeMap) {
53            if (children.count(value) == 0) {
54                return node; // This is the root node as it doesn't appear as a child
55            }
56        }
57
58        // If there's no root node found, return nullptr (this should not happen according to the problem statement)
59        return nullptr;
60    }
61};
62
1// Represents a binary tree node
2interface ITreeNode {
3    val: number;
4    left: ITreeNode | null;
5    right: ITreeNode | null;
6}
7
8// Function to create a binary tree based on the given description
9function createBinaryTree(descriptions: number[][]): ITreeNode | null {
10    // Map to store parent-to-child mappings (child = [leftChildValue, rightChildValue])
11    const nodeChildrenMap = new Map<number, [number, number]>();
12
13    // Map to check if a node is a root (has no parent)
14    const isPotentialRoot = new Map<number, boolean>();
15
16    // Iterate through the descriptions to populate the maps
17    for (const [parent, child, isLeft] of descriptions) {
18        // Destructure existing left and right children or default to 0
19        let [leftChildValue, rightChildValue] = nodeChildrenMap.get(parent) ?? [0, 0];
20
21        // Assign the child to the left or right depending on the isLeft flag
22        if (isLeft) {
23            leftChildValue = child;
24        } else {
25            rightChildValue = child;
26        }
27
28        // Mark the parent as a potential root initially
29        isPotentialRoot.set(parent, true);
30
31        // Since the current child has a parent, it's not a root
32        isPotentialRoot.set(child, false);
33
34        // Update the mappings for the parent node
35        nodeChildrenMap.set(parent, [leftChildValue, rightChildValue]);
36    }
37
38    // Function to recursively construct the tree nodes
39    const buildTree = (value: number): ITreeNode | null => {
40        // If there's no value (0), then it represents a null node
41        if (value === 0) {
42            return null;
43        }
44
45        // Get the child values
46        const [leftChildValue, rightChildValue] = nodeChildrenMap.get(value) ?? [0, 0];
47
48        // Create a new node with recursive calls for left and right children
49        return {
50            val: value,
51            left: buildTree(leftChildValue),
52            right: buildTree(rightChildValue)
53        };
54    };
55
56    // Find the root node (the one without parents) and build the tree from it
57    for (const [nodeValue, isRoot] of isPotentialRoot.entries()) {
58        if (isRoot) {
59            return buildTree(nodeValue);
60        }
61    }
62
63    // If there's no root node, return null which indicates an empty tree
64    return null;
65}
66
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following problems can be solved with backtracking (select multiple)

Time and Space Complexity

Time Complexity

The given code iterates once through the descriptions list, which results in a time complexity of O(N), where N is the number of elements (or sub-descriptions) in the descriptions array. During each iteration, the code performs a constant amount of work, including adding elements to the graph representation g and the visited set vis, as well as linking parent and child nodes. Because these operations are performed in constant time, they do not affect the overall linear time complexity.

Space Complexity

The space complexity of the algorithm is O(N) as well. This holds because the g dictionary and the vis set store each node and its connections from the descriptions. The memory used by g and vis scales linearly with the number of nodes, resulting in a linear space requirement. Additionally, the constructed tree itself has N nodes; however, this does not add to the space complexity as these nodes are already accounted for in g.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ