Grokking Tree Coding Patterns for Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Create Binary Tree From Descriptions (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You are given a 2D list called descriptions. Each element in descriptions represents a relationship in a binary tree. The element descriptions[i] = [parent<sub>i</sub>, child<sub>i</sub>, isLeft<sub>i</sub>] tells us that parent<sub>i</sub> is the paent of child<sub>i</sub>. The isLeft<sub>i</sub> value can be either 1 or 0:

  • If isLeft<sub>i</sub> is 1, childi is the left child of parent<sub>i</sub>.
  • If isLeft<sub>i</sub> is 0, child<sub>i</sub> is the right child of parent<sub>i</sub>.

Build this binary tree from the given description and return its root node.

Each node in the binary tree has a unique value.

Examples

Example 1

  • Input: descriptions = [[1, 2, 1], [1, 3, 0], [2, 4, 1]]
  • Expected Output: [1, 2, 3, 4]
Image
  • Justification: Node 1 is the root, 2 is the left child, 3 is the right child. Node 2 has 4 as its left child.

Example 2:

  • Input: descriptions = [[10, 5, 1], [10, 15, 0], [5, 3, 1], [15, 20, 0]]
  • Expected Output: [10,5,15,3,null,null,20]
Image
  • Justification: Node 10 is the root, with 5 as the left child and 15 as the right child. Node 5 has 3 as its left child, and 15 has 20 as its right child.

Example 3:

  • Input: descriptions = [[5, 3, 1], [5, 7, 0], [3, 2, 1], [3, 4, 0]]
  • Expected Output: [5,3,7,2,4]
Image
  • Justification: Node 5 is the root with 3 as the left child and 7 as the right child. Node 3 has 2 as the left child and 4 as the right child.

Constraints:

  • 1 <= descriptions.length <= 10<sup>4</sup>
  • descriptions[i].length == 3
  • 1 <= parent<sub>i</sub>, child<sub>i</sub> <= 10<sup>5</sup>
  • 0 <= isLeft<sub>i</sub> <= 1
  • The binary tree described by descriptions is valid.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible