Add All Larger Values in a BST
Updated
Problem statement
You are given the root of a binary search tree whose values are all different. Change the value of every node to its original value plus the sum of all values in the tree that are larger than it.
Keep the shape of the tree (only the values change) and return its root. The largest value stays the same, and the smallest value becomes the sum of the whole tree.
Function
greaterSumTree(root: TreeNode) → TreeNodeExamples
Example 1
root = [6,3,10,1,4,null,12]return = [28,35,22,36,32,null,12]The values in increasing order are 1, 3, 4, 6, 10, 12. Going from the largest down: 12 stays 12; 10 becomes 10 + 12 = 22; 6 becomes 6 + 22 = 28; 4 becomes 32; 3 becomes 35; 1 becomes 36. The shape does not change, so read level by level the answer is [28, 35, 22, 36, 32, null, 12].
Example 2
root = [0,-5,5]return = [5,0,5]5 is the largest, so it stays 5. 0 becomes 0 + 5 = 5. -5 becomes -5 + 0 + 5 = 0.
Example 3
root = [7]return = [7]A single node has no larger value, so it keeps its value.
Constraints
- The tree has
1to500nodes. -10^4 <= Node.val <= 10^4, and all values are different.- The tree is a valid binary search tree: every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger.
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Inorder Predecessor in a BSTNutanix · PHONE SCREENNutanix interview questions
- Shortest Path Between BST NodesGoogle · ONSITE INTERVIEWGoogle interview questions
- Validate Binary Search TreeTokopedia · ONSITE INTERVIEWTokopedia interview questions
- Check the Order of a Binary Search TreeCapital One · ONSITE INTERVIEWCapital One interview questions
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- House Robber IIIOkta · PHONE SCREENOkta interview questions
- Render a Task Tree from CSV RowsStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
- Validate Binary Search TreeKotak Mahindra Bank · PHONE SCREENKotak Mahindra Bank interview questions
- House Robber IIIGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Binary Tree Target-Sum PathsByteDance · PHONE SCREENByteDance interview questions