Convert an arbitrary Binary Tree to one that holds the Children Sum Property in its nodes

Algorithmic Approach

First, start traversing the given tree in post-order to convert it, i.e., the first change that one should do is to change the left and right children to hold the children sum property, then change the parent node. 

Let the difference between node’s data and children sum be diff. 

diff = node’s children sum - node’s data

If the value of 'diff' is 0, then the value of node data remains the same

If the value of 'diff' > 0, i.e. the value of the node's data is less than that of the node's children sum, increment the value of the node's data by diff.

If the value of 'diff' < 0, i.e. the value of the node's data, is greater than that of the node's children sum, increment the value of one child's data by diff.

Here, we can choose to increment either the left or the right child if they both have a value 

and are not NULL. 

To avoid confusion, let us decide to always first increment the left child. Since incrementing a child changes that subtree's children sum property, we need to change the left subtree as well. To do so, we keep recursively incrementing the left child. If the left child is empty, we recursively keep calling increment() for the right child.

Now, let us run the algorithm for the example mentioned above. 

First, we start by changing the left subtree (increment 9 to 10). 

Now we change the right subtree (increment 1 to 35).

Now we change the root, for which we would have to increment the left subtree for converting the root.

Here in the last step, one needs to increment 10 to 13 and fix the subtree increment 4 to 7.

C++ Implementation

/* 
    Required C++ Program to convert an arbitrary binary tree 
    to a tree that holds the children sum property 
*/
#include<bits/stdc++.h>

using namespace std;

class node {
    public:
        int data;
    node * left;
    node * right;

    node(int data) {
        this -> data = data;
        this -> left = NULL;
        this -> right = NULL;
    }
};

// Function to increment left subtree
void increment(node * node, int diff);

// Function to change the tree to hold children sum property
void convertTree(node * node) {
    int left_data = 0, right_data = 0, diff;

    // If the leaf node or the tree is empty then return true
    if (node == NULL || (node -> left == NULL && node -> right == NULL)) {
        return;
    } else {
        // Convert left and right subtrees
        convertTree(node -> left);
        convertTree(node -> right);

        // If the left child is not present then 0 is used as data for the left child
        if (node -> left != NULL) {
            left_data = node -> left -> data;
        }

        // If right child is not present then 0 is used as data of right child
        if (node -> right != NULL) {
            right_data = node -> right -> data;
        }

        // Get the diff of node's data and children sum
        diff = left_data + right_data - node -> data;

        // If a node's children sum is greater than the node's data
        if (diff > 0) {
            node -> data = node -> data + diff;
        }

        // If node's data is greater than children sum, then increment subtree by diff
        if (diff < 0) {
            increment(node, -diff); // -diff is used to make diff positive    
        }

    }
}

// Function to increment subtree by diff
void increment(node * node, int diff) {
    // IF left child is not NULL then increment it
    if (node -> left != NULL) {
        node -> left -> data = node -> left -> data + diff;
        // Recursively call to fix the descendants of node->left
        increment(node -> left, diff);
    } else if (node -> right != NULL) // Else increment right child
    {
        node -> right -> data = node -> right -> data + diff;
        // Recursively call to fix the descendants of node->right
        increment(node -> right, diff);
    }
}

// Given a binary tree, print the inorder traversal using the function printInorder()
void printInorder(node * node) {
    if (node == NULL)
        return;

    // First recur on left child
    printInorder(node -> left);

    // Then print the data of node
    cout << node -> data << " ";

    // Now recur on right child
    printInorder(node -> right);
}

// Main
int main() {
    node * root = new node(48);
    root -> left = new node(9);
    root -> right = new node(1);
    root -> left -> left = new node(4);
    root -> left -> right = new node(6);
    root -> right -> left = new node(33);
    root -> right -> right = new node(2);

    cout << "\nInorder traversal of the nodes before conversion: " << endl;
    printInorder(root);

    convertTree(root);

    cout << "\nInorder traversal of the nodes after conversion: " << endl;
    printInorder(root);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Python Implementation

# Required Python Program to convert an arbitrary binary tree 
# to a tree that holds the children sum property 

# New node class that allocates a new
# node with the given data with left and right pointers as None.									
class newNode:

	def __init__(self, key):
		self.data = key
		self.left = None
		self.right = None

# Function to change the tree to hold children sum property
def convertTree(node):

	left_data = 0
	right_data = 0
	diff=0

	# If the leaf node or the tree is empty then return true
	if (node == None or (node.left == None and node.right == None)):
		return
	
	else:
		
		# Convert left and right subtrees
		convertTree(node.left)
		convertTree(node.right)

	# If the left child is not present then 0 is used as data for the left child
	if (node.left != None):
	    left_data = node.left.data

	# If right child is not present then 0 is used as data of right child
	if (node.right != None):
		right_data = node.right.data

	# Get the diff of node's data and children sum
	diff = left_data + right_data - node.data

	# If a node's children sum is greater than the node's data
	if (diff > 0):
		node.data = node.data + diff

	# If node's data is greater than children sum, then increment subtree by diff
	if (diff < 0):
		increment(node, -diff) # -diff is used to make diff positive

# Function to increment left subtree by value of diff
def increment(node, diff):

	# IF left child is not NULL then increment it
	if(node.left != None):
		node.left.data = node.left.data + diff

		# Recursively call to fix the descendants of node->left
		increment(node.left, diff)

    # Else increment right child
	elif(node.right != None): 
		node.right.data = node.right.data + diff

		# Recursively call to fix the descendants of node.right
		increment(node.right, diff)

# Given a binary tree, print the inorder traversal using the function printInorder()
def printInorder(node):

	if (node == None):
		return

	# First recur on left child
	printInorder(node.left)

	# Then print the data of node
	print(node.data,end=" ")

	# Now recur on right child
	printInorder(node.right)

# Main
if __name__ == '__main__':
	root = newNode(48)
	root.left	 = newNode(9)
	root.right	 = newNode(1)
	root.left.left = newNode(4)
	root.left.right = newNode(6)
	root.right.left = newNode(33)
	root.right.right = newNode(2)

	print("Inorder traversal of the nodes before conversion: ")
	printInorder(root)

	convertTree(root)

	print("\nInorder traversal of the nodes after conversion: ")
	printInorder(root)

You can also try this code with Online Python Compiler

Run Code

Java Implementation

// Required Java Program to convert an arbitrary binary tree
// to a tree that holds the children's sum property 

// Binary tree node class representation
class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;
    // Function to change the tree to hold the children sum property here
    void convertTree(Node node) {
        int left_data = 0, right_data = 0, diff;

        // If the leaf node or the tree is empty then return true here
        if (node == null || (node.left == null && node.right == null)) {
            return;
        } else {
            // Convert the left and the right subtrees
            convertTree(node.left);
            convertTree(node.right);

            // If the left child is not present then 0 is used as data for the left child
            if (node.left != null) {
                left_data = node.left.data;
            }

            // If the right child is not present in the tree then 0 is used as data value of right child in the tree
            if (node.right != null) {
                right_data = node.right.data;
            }

            // Get the diff value  of the node's data and children sum
            diff = left_data + right_data - node.data;

            // If a node's children sum is greater than the node's data
            if (diff > 0) {
                node.data = node.data + diff;
            }

            // If node's data value is greater than the children's sum, then increment subtree by diff
            if (diff < 0)
                // -diff is used to make diff positive
                increment(node, -diff);
        }
    }

    // Function to increment subtree by diff
    void increment(Node node, int diff) {
        // IF left child is not NULL then increment it
        if (node.left != null) {
            node.left.data = node.left.data + diff;

            // Recursively call to fix the descendants of node->left
            increment(node.left, diff);
        } else if (node.right != null) // Else increment right child
        {
            node.right.data = node.right.data + diff;
            // Recursively call to fix the descendants of node->right
            increment(node.right, diff);
        }
    }

    // Given a binary tree, print the inorder traversal using the function printInorder()
    void printInorder(Node node) {
        if (node == null)
            return;

        // First recur on left child
        printInorder(node.left);

        // Then print the data of node
        System.out.print(node.data + " ");

        // Now recur on right child
        printInorder(node.right);
    }

}

class Main {
    public static void main(String args[]) {

        BinaryTree tree = new BinaryTree();
        tree.root = new Node(48);
        tree.root.left = new Node(9);
        tree.root.right = new Node(1);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(6);
        tree.root.right.left = new Node(33);
        tree.root.right.right = new Node(2);

        System.out.println("Inorder traversal before conversion is :");
        tree.printInorder(tree.root);

        tree.convertTree(tree.root);
        System.out.println("");

        System.out.println("Inorder traversal after conversion is :");
        tree.printInorder(tree.root);

    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Inorder traversal before conversion is :
4 9 6 48 33 1 2 
Inorder traversal after conversion is :
7 13 6 48 33 35 2

Time Complexity

O(N^2), This is the worst-case time complexity for a skewed tree where nodes are in decreasing order from root to leaf.

Space Complexity

O(N), This is the worst-case space complexity for a skewed tree where nodes are in decreasing order from root to leaf due to recursive calls taking stack space.

Frequently asked questions

Explain what a full binary tree is?

The binary tree is rooted with a maximum of 2 children in each node. 

Explain the in-order traversal of a given tree?

One can use an inorder traversal 

to make a clone of the tree. 

Can a Binary Tree be constructed using only post-order and pre-order traversal?

In some cases, it is possible to construct the Full Binary tree. 

Are the Complete Binary Tree and Full Binary Tree are same?

A full binary tree (which is also known as a correct binary tree or 2-tree) is a tree in which each and every node has two offspring save the leaves. A complete binary tree is one in which every level is filled, potentially the last, and all nodes are as far left as feasible.

Is it possible to have the same pre- and post-order traversal of a Binary Tree?

The answer is a NO. This is how an ordered tree with more than one node (for example, two nodes) looks. Pre-order traversal visits nodes in the order root-left-right, while post-order traversal visits nodes in the root-left-right.

Conclusion

In this blog, We have extensively discussed the children sum property conversion in a Binary Tree Question, which is often rated and categorised as a Medium to a Hard Level problem, and discussed the approach for the same.

To read more about Binary Tree, you can refer here to Binary Tree, Binary Tree Archives.

Recommended problems -

• Vertical Order Traversal of a Binary Tree
• Leaf Nodes in Binary Tree
• Binary Array Sorting

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses, refer to the mock test and problems; look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Learning!