Create Binary Tree From Descriptions · Interview Problem

Back to problems

Leetcode

Medium

Hash Maps

Trees

Arrays

Create Binary Tree From Descriptions

Build a binary tree from parent-child relationship triples and return its root.

Acceptance 0%

Start Practice

Problem Statement

You are given a list of descriptions, where each description has the form [parent, child, isLeft].

Each triple means that child is attached to parent as:

the left child if isLeft = 1
the right child if isLeft = 0

The descriptions describe one valid binary tree. Your task is to reconstruct the tree and return its root node.

A node value may appear multiple times across descriptions. Every node has a unique value, and exactly one node is the root of the final tree.

Input Format

descriptions[i] = [parent, child, isLeft]
parent and child are integer node values
isLeft is either 0 or 1
The descriptions form one valid binary tree

Output Format

Return the root node of the reconstructed binary tree

Constraints

The input describes exactly one valid binary tree
Node values are unique
Each description links an existing parent to one child
1 <= descriptions.length

Examples

Sample cases returned by the problem API.

Example 1

Input

descriptions = [[20,15,1],[20,17,0],[15,10,1]]

Output

root = [20,15,17,null,10]

Explanation

Node 20 has children 15 and 17. Node 15 has left child 10. The only value that never appears as a child is 20, so it is the root.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress