FastPrepValidate BST Node Descriptions

Validate BST Node Descriptions

Airbnb logoAirbnb● HardFULLTIMEOA
Learn

Problem statement

You are given an array nodes. Each row [value, left, right] describes one proposed binary-tree node:

  • value is the node's unique integer value.
  • left is the value of its left child, or -1 when it has no left child.
  • right is the value of its right child, or -1 when it has no right child.

Determine whether all rows together describe exactly one valid binary search tree. A valid description must have exactly one root, every non-root node must have exactly one parent, every referenced child must have its own row, every node must be reachable from the root, and the strict binary-search-tree ordering rule must hold for every descendant.

Return the root value when the description is valid. Otherwise, return -1.

Function

findValidBstRoot(nodes: int[][]) → int

Examples

Example 1

nodes = [[17,-1,-1],[15,13,17],[7,-1,-1],[13,-1,-1],[5,3,7],[3,-1,-1],[10,5,15]]return = 10

The rows form one connected tree rooted at 10. Every value in its left subtree is smaller, and every value in its right subtree is larger.

Example 2

nodes = [[2,3,-1],[3,-1,-1]]return = -1

Node 3 is described as the left child of 2, which violates the strict binary-search-tree ordering rule.

Constraints

  • 1 <= nodes.length <= 10^5.
  • nodes[i].length == 3.
  • 0 <= value <= 10^9, and all value entries are distinct.
  • Each child entry is -1 or an integer from 0 through 10^9.

More Airbnb problems

See Airbnb hiring insights
public int findValidBstRoot(int[][] nodes) {
  // Write your code here.
}
nodes[[17,-1,-1],[15,13,17],[7,-1,-1],[13,-1,-1],[5,3,7],[3,-1,-1],[10,5,15]]
expected10
Checking account…