Replace node with sum of children

In last two posts : Delete binary search tree and Mirror binary search tree, we discussed how we can solve many problems using just traversal of tree. Next in the series is to replace node with sum of children in binary search tree.  For example, given below tree,

replace node with sum of children in binary search tree

output will be like

replace node with sum of children in BST

 

Replace node with sum of children : Thoughts

What do we need at the root node of the given tree. It is sum of all the nodes on left subtree and all the nodes on right subtree. At this point it is clear that left and right subtree should be processed before root node is updated. This is typical postorder traversal.
One more thing to note is that to solve problem at the root, we have to first solve the problem at left and right subtree level. This is makes implementation recursive.

One important question is what should happen at the leaf nodes. There are no children, hence no sum there. One of the assumption is to keep leaf nodes as is. However, I would recommend to bring this up with interviewer before coding the solution.

What will be the process step in postorder here? Once we have sum of left subtree and right subtree, all we have to do is to update root node value to sum of both.

I would strongly recommend to shut the browser and wok out an example to understand what needs to be done and how flow works.

OK, as you are done, can we do it together. Take tree as below, and we have to replace each node of this tree with sum of children.

replace node with sum of children in binary search tree

As always, we will start with root node. Node(10) has left and right subtrees, so we will find sum of those subtrees and add it to root node and replace root node with that number. We move down to left child node(5).

At node(5), again we have left and right subtree.  Move down to left child node(1).

As node(1) is leaf node without children, we will do nothing and go back to parent node(5), return 1 to parent node.

replace node with sum of children

Back at node(5), it has right subtree, hence move to node(6).

Node(6) is leaf node, move up to parent and return 6, value of the node itself.

replace node with sum in BST

At this point, we have sum of left and right subtree of node(5). Add them both along with value at root and replace the value of node(5). Here value at node(5) becomes 12. (5+6+1)

Left subtree is processed, move up the parent node(10). Since, node(10) has right subtree, go down the right subtree.

Node(19) has left subtree, so process the left subtree first.

replace node with sum of children i binary search tree

Node(17) is leaf node, no processing, return the node value to parent node.

Back at node(19), move down to node(21).

Since, node(21) is leaf node, we should return the root value to parent node.

At this point, left and right subtrees of node(19) are already processed. So add them with root value and replace root value with result. In this case its 57. (19 + 17 + 21 ).

Finally at node(10), left and right subtrees are processed, so add sum of left and right subtree with node value, and replace node value with result. In this case it is 79.

Replace node with sum of children : Implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;

int replaceNodeWithSumOfChildren(Node *root){
	if (!root)
		return 0;
	int leftSum =  replaceNodeWithSumOfChildren(root->left);
	int rightSum = replaceNodeWithSumOfChildren(root->right);
	
	if(leftSum + rightSum != 0){
		root->value = leftSum + rightSum;
	}
	return root->value;
}

void inoderTraversal(Node * root){
	if(!root)
		return;
	
	inoderTraversal(root->left);
	printf("%d ", root->value);
	inoderTraversal(root->right);
}
Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
	
	return newNode;
}
Node *addNode(Node *node, int value){
	if(node == NULL){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}

/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,30);
	root = addNode(root,20);
	root = addNode(root,15);
	root = addNode(root,25);
	root = addNode(root,40);
	root = addNode(root,37);
	root = addNode(root,45);
	
	replaceNodeWithSumOfChildren(root);

	inoderTraversal(root);	
	return 0;
}

Java implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }

    public void inorderTraversal(){
        inorder(this.root);
    }

    private void inorder(Node root){
        if(root == null) return;

        inorder(root.left);
        System.out.println(root.value);
        inorder(root.right);
    }

    public void replaceWithSumOfChildren(){
        replaceWithSumOfChildrenRecursive(this.root);
    }

    private int replaceWithSumOfChildrenRecursive(Node root){
        if(root == null) return 0;

        boolean isLeaf = ( root.left == null && root.right == null);

        if(isLeaf) return root.value;

        //process left subtree
        int leftSum = replaceWithSumOfChildrenRecursive(root.left);
        //process right subtree
        int rightSum = replaceWithSumOfChildrenRecursive(root.right);

        root.value += leftSum + rightSum;

        return root.value;
    }
}

Test class

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTreeTests {
    public static void main (String[] args){
        BinarySearchTree binarySearchTree = new BinarySearchTree();

        binarySearchTree.insert(7);
        binarySearchTree.insert(8);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);
        binarySearchTree.insert(3);
        binarySearchTree.insert(4);

        binarySearchTree.replaceWithSumOfChildren();
        binarySearchTree.inorderTraversal();
    }
}

Complexity of recursive way to replace node with sum of children is O(n) as we will be visiting each node at least once.

Please share if there is something wrong or missing. If you are willing to contribute and share your knowledge with thousands of learners across the world, please reach out to us at communications@algorithmsandme.com