Preorder of a Special Binary Tree
Nielsen● EasyINTERNOAProblem statement
You are given an integer n and an array arr containing n positive integers. Build a special binary tree, replace its special values with zero, and return its preorder traversal.
Build the tree
- Sort
arrin ascending order. Keep every occurrence of a repeated value. - For each nonempty sorted segment, choose its lower middle element as the root. For a segment of length
m, its zero-based index within that segment is(m - 1) / 2, using integer division. - Build the left subtree from the elements before that root and the right subtree from the elements after it. Apply the same rule to each segment.
Replace special values
For each original node value x, let last = x % 10 and remaining = x / 10, using integer division. Replace x with 0 exactly when:
remaining + remaining * last + last == xReplacement changes only the node value. Keep the tree shape fixed; do not sort or rebuild the tree after replacement.
Read the traversal
Return the values in preorder: root, then the left subtree, then the right subtree.
Function
processData(n: int, arr: int[]) → int[]Examples
Example 1
n = 8arr = [12,8,7,16,19,41,33,29]return = [16,0,0,12,0,0,33,41]Sorting gives [7,8,12,16,19,29,33,41]. Choosing the lower middle at every step gives the original preorder [16,8,7,12,29,19,33,41].
The special values are 7, 8, 19, and 29. For example, 2 + 2 * 9 + 9 = 29. Replacing them gives [16,0,0,12,0,0,33,41].
Example 2
n = 4arr = [1,51,23,49]return = [23,0,0,51]Sorting gives [1,23,49,51]. The lower middle is 23, so the original preorder is [23,1,49,51].
1 is special because 0 + 0 * 1 + 1 = 1. 49 is special because 4 + 4 * 9 + 9 = 49. The result is [23,0,0,51].
Example 3
n = 4arr = [12,9,12,19]return = [12,0,12,0]Sorting gives [9,12,12,19]. Both copies of 12 are kept. The original preorder is [12,9,12,19], and replacing 9 and 19 gives [12,0,12,0].
Constraints
1 <= n <= 1000arr.length == n1 <= arr[i] <= 10^9- Array values may repeat.