Create Binary Tree From Descriptions - Practice Coding Problems

Create Binary Tree From Descriptions - Problem

You are given a 2D integer array descriptions where descriptions[i] = [parent_i, child_i, isLeft_i] indicates that parent_i is the parent of child_i in a binary tree of unique values.

Furthermore:

If isLeft_i == 1, then child_i is the left child of parent_i.
If isLeft_i == 0, then child_i is the right child of parent_i.

Construct the binary tree described by descriptions and return its root.

The test cases will be generated such that the binary tree is valid.

Input & Output

Example 1 — Basic Tree

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

› Output: [50,20,80,15,17,19]

💡 Note: Root is 50. Left child 20 has children 15 (left) and 17 (right). Right child 80 has left child 19.

Example 2 — Simple Tree

$ Input: descriptions = [[1,2,1],[1,3,0],[2,4,1],[2,5,0]]

› Output: [1,2,3,4,5]

💡 Note: Root is 1. Left child is 2 with children 4 and 5. Right child is 3.

Example 3 — Single Root

$ Input: descriptions = [[39,70,1]]

› Output: [39,70]

💡 Note: Simple tree with root 39 and single left child 70.

Constraints

1 ≤ descriptions.length ≤ 10⁴
descriptions[i].length == 3
1 ≤ parent_i, child_i ≤ 10⁵
isLeft_i is either 0 or 1
The binary tree described by descriptions is valid

Visualization

Tap to expand

Understanding the Visualization

Input

Array of [parent, child, isLeft] relationships

Process

Build nodes and connect parent-child links

Output

Binary tree with identified root node

Key Takeaway

🎯 Key Insight: The root is the only node value that never appears as a child in any relationship description

Asked in

M Microsoft 35 a Amazon 28 f Facebook 22 G Google 18

The key insight is that the root node never appears as a child in any relationship. Use a hash map for O(1) node lookups and track children to identify the root efficiently. Best approach is Hash Map Optimization. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Node Creation	O(n²)	O(n)	Create nodes on demand and search for connections repeatedly
Hash Map Optimization	O(n)	O(n)	Use hash map for O(1) node lookups during tree construction

Brute Force Node Creation — Algorithm Steps

Step 1: For each description, create parent and child nodes
Step 2: Connect parent-child relationships
Step 3: Find root by checking which node never appears as child

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Nodes

For each relationship, search existing nodes or create new ones

Connect Relations

Set parent-child connections and track children

Find Root

Root is the node that never appears as a child

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct TreeNode* solution(int** descriptions, int descriptionsSize) {
    struct TreeNode* nodes[1000];
    int nodeCount = 0;
    int children[100000] = {0};
    
    struct TreeNode* findNode(int val) {
        for (int i = 0; i < nodeCount; i++) {
            if (nodes[i]->val == val) {
                return nodes[i];
            }
        }
        struct TreeNode* newNode = createNode(val);
        nodes[nodeCount++] = newNode;
        return newNode;
    }
    
    for (int i = 0; i < descriptionsSize; i++) {
        int parentVal = descriptions[i][0];
        int childVal = descriptions[i][1];
        int isLeft = descriptions[i][2];
        
        struct TreeNode* parent = findNode(parentVal);
        struct TreeNode* child = findNode(childVal);
        children[childVal] = 1;
        
        if (isLeft == 1) {
            parent->left = child;
        } else {
            parent->right = child;
        }
    }
    
    for (int i = 0; i < nodeCount; i++) {
        if (!children[nodes[i]->val]) {
            return nodes[i];
        }
    }
    
    return NULL;
}

int main() {
    int descriptions[100][3];
    int size = 0;
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            descriptions[size][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            descriptions[size][1] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            descriptions[size][2] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr == ']') ptr++;
            if (*ptr == ',') ptr++;
            size++;
        } else {
            ptr++;
        }
    }
    
    int* desc_ptrs[100];
    for (int i = 0; i < size; i++) {
        desc_ptrs[i] = descriptions[i];
    }
    
    struct TreeNode* result = solution(desc_ptrs, size);
    
    printf("[%d]\n", result ? result->val : 0);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n descriptions, we may need to search through all created nodes to find existing ones

⚠ Quadratic Growth

Space Complexity

O(n)

Store all n nodes in the tree

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Node Creation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler