Replace BST nodes with the sum of nodes greater than or equal to the node

Question

I would like to know the algorithm for the following problem:
"Given a BST(There can be duplicate nodes), replace every node with value which is sum of values of all nodes greater than equal to the current node."

Example:

                              5                15
                            2  10     o/p:   17  10

I did it with reverse in-order traversal keeping a variable 'sum'. Here is the code:

public static void replaceNodeValue(BSTNode root, int[] sum) {  
if (root == null) return;       
replaceNodeValue(root.right, sum);      
root.data = (sum[0] = sum[0] + root.data);      
replaceNodeValue(root.left, sum);
}

The problem is this code works only if the tree doesn't contain a duplicate node. I am looking for the correct algorithm which will handle duplicate nodes also.

One case for which the code will fail is:

                               5
                            5     5

Please help. Thanks

Answer 1

You need to have an object with a field name sum. As you go, you will update this sum. My solution is a recursive one. Considering the fact that we are dealing with a sorted tree (binary search tree), you need to traverse the right child first, then update the current node and sum. Then, traverse the left child. By the end of recursion, the existing root will be the root of the Greater Sum Tree (each node has the summation of the values of the nodes greater than or equal to the same node).

/**
 * Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.
 * <p>
 * As a reminder, a binary search tree is a tree that satisfies these constraints:
 * <p>
 * The left subtree of a node contains only nodes with keys less than the node's key.
 * The right subtree of a node contains only nodes with keys greater than the node's key.
 * Both the left and right subtrees must also be binary search trees.
 * Reference: LeetCode
 */
public class BinarySearchTreeToGreaterSumTree {

    class Sum {
        public int sum = 0;
    }

    public static void main(String[] args) {
/*
public class TreeNode {

    Integer val;
    TreeNode left;
    TreeNode right;

    TreeNode(Integer x) {
        val = x;
    }

    TreeNode(TreeNode treeNode) {
        if (treeNode != null) {
            this.val = treeNode.val;
            this.left = new TreeNode(treeNode.left);
            this.right = new TreeNode(treeNode.right);
        }
    }

}
 */
        TreeNode node0 = new TreeNode(0);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        node4.left = node1;
        node4.right = node6;
        node1.left = node0;
        node1.right = node2;
        node2.right = node3;
        node6.left = node5;
        node6.right = node7;
        node7.right = node8;

        BinarySearchTreeToGreaterSumTree bstToGST = new BinarySearchTreeToGreaterSumTree();
        // the input of this method should be the root of the tree
        TreeNode result = bstToGST.bstToGst(node4);
        System.out.println();
    }

    /**
     * Builds a GST.
     *
     * @param root The root of the binary search tree
     * @return The GST
     */
    public TreeNode bstToGst(TreeNode root) {
        if (root != null) {
            Sum sum = new Sum();
            buildGST(root, sum);
        }
        return root;
    }

    /**
     * A recursive method to build the Greater Sum Tree.
     *
     * @param currentNode The current node
     * @param sum         The current summation
     */
    private void buildGST(TreeNode currentNode, Sum sum) {
        if (currentNode == null)
            return;
        // Call build GST on the right child
        TreeNode r = currentNode.right;
        buildGST(r, sum);
        // Update the current sum with the value of the current node
        sum.sum = sum.sum + currentNode.val;
        // Update the value of the current node with the new sum
        currentNode.val = sum.sum;
        // Call build GST on the left child with the updated sum
        TreeNode l = currentNode.left;
        buildGST(l, sum);
    }

}

I hope it helps.

Answer 2

Here is the complete program in java

BinarySearchTree class definition

public class BST<T> {

public Node root;

 static class Node<T>{
 public Node left;  
 public Node right;
 public T data;

 Node(T data){
     this.data =data;
 }
}

}

Actual class definition which is doing real stuff where each node replaced with the sum of all greater nodes in a given BST

public class TestGreaterNodeBST {



    public static void main(String[] args) {
        BST<Integer> bst = new BST<Integer>();
        bst.root= new BST.Node<Integer>(50);
        bst.root.left =new BST.Node<Integer>(30);
        bst.root.right =new BST.Node<Integer>(80);
        bst.root.right.left =new BST.Node<Integer>(70);
        bst.root.right.left.left =new BST.Node<Integer>(60);
        bst.root.right.right =new BST.Node<Integer>(100);
        bst.root.right.right.right =new BST.Node<Integer>(120);
        bst.root.right.right.right.left =new BST.Node<Integer>(110);
        bst.root.right.right.right.right =new BST.Node<Integer>(150);

        printInOrderDescending(bst.root);
        System.out.println();
        System.out.println();
        transformToGreaterNode(bst.root, 0);
        printInOrderDescending(bst.root);

    }


    static void printInOrderDescending(BST.Node node){

        if(node==null){
            return;
        }

        printInOrderDescending(node.right);
        System.out.println(node.data);
        printInOrderDescending(node.left);

    }



    static Integer transformToGreaterNode(BST.Node<Integer> node, Integer sum){

        if(node==null){
            return sum;
        }


        sum = transformToGreaterNode(node.right, sum);

        Integer data = node.data;
        node.data=sum;
        sum = sum + data;

        sum = transformToGreaterNode(node.left, sum);

        return sum;
    }

}

Answer 3

Algo:

Do reverse in order traversal, and update sum

Here is the java implementation

public static void modifyWithSumOfGreaterNodes(BinaryTreeNode<Integer> bst) {
    doModifyWithSumOfGreaterNodes(bst, new MutableInteger(0));      
}

private static void doModifyWithSumOfGreaterNodes(BinaryTreeNode<Integer> bst, MutableInteger sum) {
    if (bst == null) {
        return ;
    }

    doModifyWithSumOfGreaterNodes(bst.getRight(), sum);
    sum.add(bst.getData());
    bst.setData(sum.getValue());
    doModifyWithSumOfGreaterNodes(bst.getLeft(), sum);      
}

Here is the unit test

@Test
public void replaceBSTNodesWithSumOfNodesGreaterOrEqualToNodeTest() {

    BinaryTreeNode<Integer> eighty = new BinaryTreeNode<Integer>(80);
    BinaryTreeNode<Integer> sixty = new BinaryTreeNode<Integer>(60);
    BinaryTreeNode<Integer> forty = new BinaryTreeNode<Integer>(40);
    BinaryTreeNode<Integer> twenty = new BinaryTreeNode<Integer>(20);
    BinaryTreeNode<Integer> seventy = new BinaryTreeNode<Integer>(70, sixty, eighty);
    BinaryTreeNode<Integer> thrity = new BinaryTreeNode<Integer>(30, twenty, forty);
    BinaryTreeNode<Integer> root = new BinaryTreeNode<Integer>(50, thrity, seventy);

    BinaryTreeUtil.modifyWithSumOfGreaterNodes(root);

    assertThat(BinaryTreeUtil.iPostOrder(root).toArray(new Integer[0]), equalTo(new Integer[]{350,300,330,210,80,150,260}));


}

Answer 4

This problem can be solved recursively, the idea behind it being:

For any node in a BST:

• the right sub-tree has all elements greater than or equal to the parent.
• the left sub-tree has elements of value less than the parent.

With this is mind,

• For each node, we replace the value of it with the sum of it's right sub-tree + it's own value. (We calculate the sum of the right sub-tree recursively :) )

• Thereafter we go-to it's left child and replace it's value with it's parent's value + it's own value + it's right sub-tree's max sum.

The terminating condition for the recursion happens when we encounter a node without a right sub-tree. When this happens, the value of the node would be it's own value and we return.

The C/C++ ish pseudo code:

NODE* recSum(root){
    getSum(root);
    return root;
}

int getSum(NODE *n){
    if (n->r == NULL) return n->val;

    else{
        n->val = getSUM(n->r) + n->val;
        n->l->val = getSUM(n) + getSUM((n->l)->r);
    }
}

Answer 5

Here is a O(n) solution to the problem. Visit each node and the values greater than the number by traversing the tree for each node.Since the Tree needs to be visited for all nodes the complexity will be O(n)

int sum_all(Node root)
{
    if(root == null) return 0;
    return root.data + sum_all(root.left) + sum_all(root.right);
}

void replace_keys(Node root, int total)
{
    if(root == null) return;

    int leftsum = sum_all(root.left);
    root.data = (total - leftsum - root.data);

    replace_keys(root.left, total);
    replace_keys(root.right, total);
}

void replace_keys(Node root)
{
    int total = sum_all(root);
    replace_keys(root, total);
}

Answer 6

First, traversal the BST and push every node into a array.

Second,sort the array.

Finally, traversal the BST again and do the replacement with the help of the array.