Technical Interview Question

You are given a Binary Search Tree (BST) where each node contains an integer value. Your task is to convert this BST into a "Greater Tree", which is a BST where every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Write a function convertBST to perform this conversion and return the modified BST.

function TreeNode(val, left, right) {
   this.val = (val===undefined ? 0 : val)
   this.left = (left===undefined ? null : left)
   this.right = (right===undefined ? null : right)
}

function convertBST(root) {
    // Your code here
}

Example:

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

Output: 
       15
     /    \
    21     13
   / \    /  \
  21  23 18   7

Answer

Here is the step-by-step detailed explanation of the code to convert the given BST into a "Greater Tree":

function convertBST(root) {
    let sum = 0;

    // Reverse in-order traversal to update each node with the sum of all greater elements
    function reverseInOrderTraversal(node) {
        if (node === null) {
            return;
        }

        // Traverse the right subtree
        reverseInOrderTraversal(node.right);

        // Update the sum
        sum += node.val;

        // Update the current node value
        node.val = sum;

        // Traverse the left subtree
        reverseInOrderTraversal(node.left);
    }

    // Perform the reverse in-order traversal starting from the root
    reverseInOrderTraversal(root);

    // Return the modified BST
    return root;
}

The convertBST function first initializes a variable sum to 0. It then defines a helper function reverseInOrderTraversal, which performs a reverse in-order traversal of the BST. In this traversal, it visits the right subtree, updates the sum by adding the node value, and updates the current node value with the new sum. Then it traverses the left subtree.

After defining the helper function, the convertBST function calls the reverseInOrderTraversal with the root of the BST. Finally, it returns the modified BST.

The time complexity of this solution is O(n), where n is the number of nodes in the BST. This is because the solution visits every node once in the reverse in-order traversal.