How should I practice Validate Binary Search Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Goldman Sachs online assessment problems in FastPrep.

Is Validate Binary Search Tree associated with Goldman Sachs?

FastPrep tags this as a Goldman Sachs coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Tree

Validate Binary Search Tree

Learn this problem

● MediumGoldman SachsONSITE INTERVIEW

Problem statement

A binary tree is represented by aligned arrays. Node i has value values[i]; left[i] and right[i] contain child indices, or -1 when that child is absent. The index root identifies the root node.

Return true if the tree is a valid binary search tree and false otherwise.

For every node, every value in its left subtree must be strictly smaller and every value in its right subtree must be strictly greater. Therefore duplicate values make the tree invalid.

Function

isValidBST(values: int[], left: int[], right: int[], root: int) → boolean

Examples

Example 1

values = [2,1,3]left = [1,-1,-1]right = [2,-1,-1]root = 0return = true

The left value 1 is smaller than 2, and the right value 3 is greater.

Example 2

values = [5,1,4,3,6]left = [1,-1,3,-1,-1]right = [2,-1,4,-1,-1]root = 0return = false

Node value 4 lies in the right subtree of 5 but is not greater than 5.