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

0% completed

Vote For New Content
Create Binary Tree From Descriptions (medium)
On this page

Problem Statement

Examples

Try it yourself

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!

On this page

Problem Statement

Examples

Try it yourself