How should I practice Transform and Prune a Mode-Valued Binary Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen problems in FastPrep.

Is Transform and Prune a Mode-Valued Binary Tree associated with Google?

FastPrep tags this as a Google phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Transform and Prune a Mode-Valued Binary Tree

Learn this problem

● Medium

GoogleINTERNPHONE SCREEN

See Google hiring insights

Problem statement

You are given a binary tree as a node table nodes. Row i is [value, leftIndex, rightIndex]; child index -1 means that child is absent, and row 0 is the root.

Find the mode of the original node values. If several values have the same maximum frequency, use the smallest such value. Remove every node whose original value equals the mode, together with its entire subtree.

For every retained node, replace a nonzero value x with 1 / x, leave a zero value unchanged, and swap its left and right child pointers. Mode comparisons always use the original values, before any reciprocal replacement.

Return the retained tree as a new node table in breadth-first order, with child indices reindexed for that returned table. Return an empty table if the input is empty or the root is removed.

Function

transformModeTree(nodes: double[][]) → double[][]

Examples

Example 1

nodes = [[4,1,2],[0,-1,-1],[2,3,4],[2,-1,-1],[3,-1,-1]]return = [[0.25,-1,1],[0,-1,-1]]

Value 2 is the unique mode, so node 2 and its whole subtree are removed. The root becomes 0.25, and its original left child with value 0 moves to the right and remains 0.

Example 2

nodes = [[4,1,2],[2,-1,-1],[3,-1,-1]]return = [[0.25,1,-1],[0.3333333333333333,-1,-1]]

All three values occur once, so the smallest tied value, 2, is the mode. After the root swaps its children, the node with value 3 is retained on the left while the node with value 2 is removed.

Example 3

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

Value 2 is the mode and appears at the root, so the root and the entire tree are removed.

Example 4

nodes = []return = []

An empty input tree produces an empty output table.

Constraints

0 <= nodes.length <= 500
Every row has exactly three finite numbers [value, leftIndex, rightIndex].
Each value is between -10^6 and 10^6, inclusive, and has at most six digits after the decimal point. Signed zero is treated as 0.
Each child index is the integer -1 or an integer in [0, nodes.length - 1].
For a nonempty input, row 0 is the root; every other row is reachable exactly once, so the table represents one valid binary tree.