How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find mode in a trinary search tree | Google Coding Question

Find mode in a trinary search tree

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given the root of a **trinary search tree** where each node has up to three children: ```text class Node { int val; Node left; // all values < val Node middle; // all values = val Node right; // all values > val } ``` Assume the tree is intended to satisfy the ordering rules above. ## Task Return the **mode(s)** of the tree: the value(s) that occur most frequently among all nodes. - If there is one mode, return a single-element list. - If multiple values tie for highest frequency, return **all** such values (in any order). ## Constraints (typical) - Number of nodes `n` can be large (e.g., up to `10^5`). - Values can be any 32-bit signed integers. ## Follow-up How would your approach change if the tree is **broken** (i.e., it may not respect the `<`, `=`, `>` constraints), but you still must return the correct mode(s)?

Quick Answer: This question evaluates a candidate's understanding of tree data structures and frequency analysis, focusing on handling a trinary search tree variant and determining mode values across possibly large datasets.

Part 1: Find Mode(s) in a Valid Trinary Search Tree

You are given a valid trinary search tree. Each node has an integer value and up to three children: left, middle, and right. For every node, all values in its left subtree are strictly less than the node's value, all values in its middle subtree are equal to the node's value, and all values in its right subtree are strictly greater than the node's value. The tree is encoded using parallel arrays instead of Node objects. Return the value or values that occur most frequently in the tree. To make the output deterministic, return the modes in increasing order. If the tree is empty, return an empty list.

Constraints

0 <= n <= 100000, where n == len(values)
len(left) == len(middle) == len(right) == n
Each child index is either -1 or an integer in [0, n - 1]
root == -1 if n == 0; otherwise 0 <= root < n
The nodes reachable from root form a valid tree with no cycles
The tree satisfies the trinary search ordering rules recursively
Each value is a 32-bit signed integer

Examples

Input: ([], [], [], [], -1)

Expected Output: []

Explanation: The tree is empty, so there are no modes.

Input: ([42], [-1], [-1], [-1], 0)

Expected Output: [42]

Explanation: A single-node tree has that node's value as the only mode.

Input: ([0, -2147483648, 2147483647], [1, -1, -1], [-1, -1, -1], [2, -1, -1], 0)

Expected Output: [-2147483648, 0, 2147483647]

Explanation: All three values occur once, so they all tie as modes.

Input: ([5, 3, 5, 7, 5], [1, -1, -1, -1, -1], [2, -1, 4, -1, -1], [3, -1, -1, -1, -1], 0)

Expected Output: [5]

Explanation: Value 5 occurs three times, while 3 and 7 occur once.

Input: ([10, 4, 10, 12, 4], [1, -1, -1, -1, -1], [2, 4, -1, -1, -1], [3, -1, -1, -1, -1], 0)

Expected Output: [4, 10]

Explanation: Values 4 and 10 each occur twice, tying for highest frequency.

Hints

In a valid trinary search tree, an inorder traversal using left, node, middle, right visits values in nondecreasing order.
Because equal values appear consecutively during that traversal, you can track only the current run length and the best run length so far.

Part 2: Find Mode(s) in a Broken Trinary Tree

You are given a trinary tree with integer values. Each node has up to three children: left, middle, and right. Unlike a valid trinary search tree, this tree may be broken: the left, middle, and right children do not necessarily follow any ordering rules. Return the value or values that occur most frequently among all reachable nodes. To make the output deterministic, return the modes in increasing order. If the tree is empty, return an empty list.

Constraints

0 <= n <= 100000, where n == len(values)
len(left) == len(middle) == len(right) == n
Each child index is either -1 or an integer in [0, n - 1]
root == -1 if n == 0; otherwise 0 <= root < n
The nodes reachable from root form a tree with no cycles
No ordering rule is guaranteed between a node and its children
Each value is a 32-bit signed integer

Examples

Input: ([], [], [], [], -1)

Expected Output: []

Explanation: The tree is empty, so there are no modes.

Input: ([-2147483648], [-1], [-1], [-1], 0)

Expected Output: [-2147483648]

Explanation: A single-node tree has that node's value as the only mode.

Input: ([5, 8, 1, 8, 5, 8], [1, -1, 4, -1, -1, -1], [2, -1, -1, -1, -1, -1], [3, -1, -1, -1, 5, -1], 0)

Expected Output: [8]

Explanation: The tree violates trinary search ordering, but counting all nodes shows that 8 occurs three times.

Input: ([2, 1, 3, 1, 3, 4], [1, -1, 4, -1, -1, -1], [-1, -1, -1, -1, -1, -1], [2, 3, 5, -1, -1, -1], 0)

Expected Output: [1, 3]

Explanation: Values 1 and 3 each occur twice, tying for highest frequency.

Input: ([0, 2147483647, -2147483648], [1, -1, -1], [-1, -1, -1], [2, -1, -1], 0)

Expected Output: [-2147483648, 0, 2147483647]

Explanation: All values occur once, even though the child ordering is broken.

Hints

Without the ordering property, equal values are not guaranteed to be adjacent in any traversal.
Use a frequency table while traversing the entire tree.

Quick Overview

This question evaluates a candidate's understanding of tree data structures and frequency analysis, focusing on handling a trinary search tree variant and determining mode values across possibly large datasets.