Subtree Sum Balanced Nodes in Binary Search Tree
Given the preorder traversal array of a Binary Search Tree (BST) containing unique integer keys and a non-negative integer threshold k, reconstruct the original BST. For each node in the tree, calculate the absolute difference between the sum of keys in its left subtree and the sum of keys in its right subtree. If a subtree is empty, its sum is considered to be 0.
Return a JSON array of keys for all nodes whose left and right subtree sum absolute difference is at most k. The returned array must be sorted in ascending order.
[ "[5, 3, 2, 4, 8, 7, 9]", "2" ]
[ 2, 3, 4, 7, 8, 9 ]
Explanation. Node 5 has left sum 9 and right sum 24 (diff 15 > 2). Node 3 has left sum 2 and right sum 4 (diff 2 <= 2). Node 8 has left sum 7 and right sum 9 (diff 2 <= 2). Leaf nodes 2, 4, 7, 9 have left and right sums of 0 (diff 0 <= 2). Valid nodes sorted are [2, 3, 4, 7, 8, 9].
[ "[10, 5, 1, 7, 15]", "3" ]
[ 1, 7, 10, 15 ]
Explanation. Node 10 has left sum 13 and right sum 15 (diff 2 <= 3). Node 5 has left sum 1 and right sum 7 (diff 6 > 3). Leaves 1, 7, 15 have diff 0 <= 3. The valid nodes are 1, 7, 10, 15.
[ "[4, 2, 1, 3, 6, 5, 7]", "0" ]
[ 1, 3, 5, 7 ]
Explanation. Only nodes with an absolute subtree sum difference of 0 are included. These are all the leaf nodes: 1, 3, 5, and 7.
[ "[10]", "0" ]
[ 10 ]
Explanation. The single root node has left sum 0 and right sum 0 (diff 0 <= 0), so node 10 is returned.
[ "[1, 2, 3]", "3" ]
[ 2, 3 ]
Explanation. The tree is a right skewed line: 1 -> 2 -> 3. Node 1 has left sum 0 and right sum 5 (diff 5 > 3). Node 2 has left sum 0 and right sum 3 (diff 3 <= 3). Node 3 has diff 0 <= 3. Valid nodes are [2, 3].
Follow-up: Can you perform the BST reconstruction and compute all node subtree sums in linear O(N) time?
1 <= preorder.length <= 10^4 -10^5 <= preorder[i] <= 10^5 All elements in preorder are unique. 0 <= k <= 10^9