Pular para o conteúdo principal

Level Up Binary Search Tree

Given the reference to a binary search tree, "level-up" the tree. Leveling-up the tree consists of modifying every node in the tree such that every node's value increases by the sum of all the node's values that are larger than it.

Note: The tree will only contain unique values and you may assume that it is a valid binary search tree.

Example(s)​

Example 1:

Input:
      0
       \
        3

Output:
      3
       \
        3

Explanation:
- Node 3: No nodes larger than 3, so value stays 3
- Node 0: Sum of nodes larger than 0 is 3, so 0 + 3 = 3

Example 2:

Input:
      2
    /   \
   1     3

Output:
      5
    /   \
   6     3

Explanation:
- Node 3: No nodes larger than 3, so value stays 3
- Node 2: Sum of nodes larger than 2 is 3, so 2 + 3 = 5
- Node 1: Sum of nodes larger than 1 is 3 + 2 = 5, so 1 + 5 = 6

Example 3:

Input:
        4
      /   \
     2     6
    / \   / \
   1   3 5   7

Output:
        22
      /    \
     27     16
    /  \    /  \
   28  24  21   7

Explanation:
- Process in reverse in-order: 7, 6, 5, 4, 3, 2, 1
- Node 7: 7 + 0 = 7
- Node 6: 6 + 7 = 13, but we need to add sum of larger values before modification
  Actually, we add the sum of original larger values:
  - Node 7: 7 (no larger, stays 7)
  - Node 6: 6 + 7 = 13... wait, let me recalculate
  Actually, the algorithm is: for each node, add sum of all original values larger than it
  - Node 7: 7 + 0 = 7
  - Node 6: 6 + 7 = 13
  - Node 5: 5 + 7 + 6 = 18
  - Node 4: 4 + 7 + 6 + 5 = 22
  - Node 3: 3 + 7 + 6 + 5 + 4 = 25
  - Node 2: 2 + 7 + 6 + 5 + 4 + 3 = 27
  - Node 1: 1 + 7 + 6 + 5 + 4 + 3 + 2 = 28

Solution​

The solution uses a reverse in-order traversal (right, root, left) of the BST:

  1. Traverse the right subtree first (largest values)
  2. Process the current node by adding the accumulated sum of larger values
  3. Update the accumulated sum to include the current node's original value
  4. Traverse the left subtree (smaller values)

This approach leverages the BST property: in-order traversal gives sorted values, so reverse in-order gives values in descending order.

JavaScript Solution

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/

/**
* Level up a BST by adding sum of all larger values to each node
* @param {TreeNode} root - Root of the binary search tree
* @return {TreeNode} - Modified tree (modifies in place)
*/
function levelUpBST(root) {
let sum = 0; // Accumulated sum of all values larger than current node

function reverseInOrder(node) {
  if (!node) return;
  
  // Traverse right subtree first (larger values)
  reverseInOrder(node.right);
  
  // Process current node: add sum of all larger values
  const originalVal = node.val;
  node.val += sum;
  
  // Update sum to include this node's original value
  sum += originalVal;
  
  // Traverse left subtree (smaller values)
  reverseInOrder(node.left);
}

reverseInOrder(root);
return root;
}

// Helper function to create a tree node
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}

// Helper function to print tree (in-order)
function printInOrder(root) {
if (!root) return [];
return [...printInOrder(root.left), root.val, ...printInOrder(root.right)];
}

// Test case 1: [0, null, 3]
const tree1 = new TreeNode(0);
tree1.right = new TreeNode(3);
levelUpBST(tree1);
console.log('Example 1:', printInOrder(tree1)); // [3, 3]

// Test case 2: [2, 1, 3]
const tree2 = new TreeNode(2);
tree2.left = new TreeNode(1);
tree2.right = new TreeNode(3);
levelUpBST(tree2);
console.log('Example 2:', printInOrder(tree2)); // [6, 5, 3]

// Test case 3: [4, 2, 6, 1, 3, 5, 7]
const tree3 = new TreeNode(4);
tree3.left = new TreeNode(2);
tree3.right = new TreeNode(6);
tree3.left.left = new TreeNode(1);
tree3.left.right = new TreeNode(3);
tree3.right.left = new TreeNode(5);
tree3.right.right = new TreeNode(7);
levelUpBST(tree3);
console.log('Example 3:', printInOrder(tree3)); // [28, 27, 25, 22, 18, 13, 7]
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Iterative)​

Here's an iterative approach using a stack:

/**
 * Level up BST using iterative reverse in-order traversal
 * @param {TreeNode} root - Root of the binary search tree
 * @return {TreeNode} - Modified tree
 */
function levelUpBSTIterative(root) {
  let sum = 0;
  const stack = [];
  let current = root;
  
  while (current || stack.length > 0) {
    // Go to the rightmost node
    while (current) {
      stack.push(current);
      current = current.right;
    }
    
    // Process the node
    current = stack.pop();
    const originalVal = current.val;
    current.val += sum;
    sum += originalVal;
    
    // Move to left subtree
    current = current.left;
  }
  
  return root;
}

Complexity​

  • Time Complexity: O(n) - Where n is the number of nodes. We visit each node exactly once.
  • Space Complexity: O(h) - Where h is the height of the tree. For recursive solution, this is the recursion stack. For iterative solution, this is the stack size. In the worst case (skewed tree), this is O(n), but for a balanced tree it's O(log n).

Approach​

The solution leverages the BST property and uses reverse in-order traversal:

  1. BST Property: In a BST, in-order traversal gives values in ascending order. Reverse in-order (right, root, left) gives values in descending order.

  2. Reverse In-Order Traversal:

    • Process right subtree first (largest values)
    • Process current node
    • Process left subtree (smallest values)

  3. Accumulation Strategy:

    • Maintain a running sum of all values processed so far
    • When processing a node, add the accumulated sum (which contains all larger values)
    • Update the sum to include the current node's original value

  4. In-Place Modification: The tree is modified in place, which is space-efficient.

Key Insights​

  • Reverse in-order traversal is the key - it processes nodes from largest to smallest
  • Accumulation pattern: By maintaining a sum as we traverse, we naturally accumulate all larger values
  • BST property utilization: The sorted nature of BST makes this problem solvable in O(n) time
  • Single pass: We only need one traversal through the tree
  • In-place modification: No need to create a new tree structure

Step-by-Step Example​

Let's trace through Example 2: [2, 1, 3]

Initial tree:
      2
    /   \
   1     3

Reverse in-order traversal order: 3 → 2 → 1

Step 1: Process node 3 (rightmost)
  - sum = 0 (no larger values)
  - node.val = 3 + 0 = 3
  - sum = 0 + 3 = 3

Step 2: Process node 2 (root)
  - sum = 3 (larger values: 3)
  - node.val = 2 + 3 = 5
  - sum = 3 + 2 = 5

Step 3: Process node 1 (leftmost)
  - sum = 5 (larger values: 3, 2)
  - node.val = 1 + 5 = 6
  - sum = 5 + 1 = 6

Final tree:
      5
    /   \
   6     3

Edge Cases​

  • Single node: Tree with one node remains unchanged (no larger values)
  • All left children: Skewed tree to the left - still works correctly
  • All right children: Skewed tree to the right - still works correctly
  • Empty tree: Returns null/None
  • Large values: Works with any integer values

Takeaways​

  • BST properties can be leveraged for efficient solutions
  • Reverse in-order traversal is useful when processing from largest to smallest
  • Accumulation pattern is common in tree problems
  • Single traversal is often possible with careful design
  • In-place modification saves space when the problem allows it