FastPrepCreate a Binary Tree from Parent-Child Descriptions

Create a Binary Tree from Parent-Child Descriptions

Amazon logoAmazon● MediumNEW GRADPHONE SCREEN
Learn

Problem statement

You are given an array descriptions. Each entry has the form [parent, child, isLeft] and describes one edge in a binary tree:

  • If isLeft is 1, child is the left child of parent.
  • If isLeft is 0, child is the right child of parent.

The descriptions may appear in any order, so an entry can mention a child before the entry that connects its parent to the rest of the tree.

Build the described binary tree and return its root.

Function

createBinaryTree(descriptions: int[][]) → TreeNode

Examples

Example 1

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

50 is the only value that never appears as a child. Its children are 20 and 80; the remaining descriptions attach 15, 17, and 19.

Example 2

descriptions = [[3,4,1],[1,2,1],[1,3,0]]return = [1,2,3,null,null,4]

The first description initially forms a separate subtree rooted at 3. The last description connects that subtree as the right child of 1.

Constraints

  • descriptions is non-empty.
  • Every entry contains exactly three integers in the form [parent, child, isLeft].
  • isLeft is either 0 or 1.
  • Node values uniquely identify nodes.
  • The descriptions define exactly one valid, non-empty binary tree.

More Amazon problems

See Amazon hiring insights
public TreeNode createBinaryTree(int[][] descriptions) {
    // Write your code here.
}
descriptions[[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
expected[50,20,80,15,17,19]
Checking account…