Fix children-sum property in a binary tree
Write an efficient algorithm to fix the children-sum property in a given binary tree. The only operation allowed is an increment operation on the node’s value.
For a tree to satisfy the children-sum property, each node’s value should be equal to the sum of values at its left and right subtree. The value of an empty node is considered as 0.
For example, the binary tree on the left below does not hold the children-sum property. It should be converted into a binary tree on the right that hold that property.
1. Preorder Traversal
The idea is to traverse the binary tree in a preorder fashion, i.e., fix the left and right subtree to hold the children-sum property before processing the node. Then for each node, calculate the difference between the root and its children.
- If the node is less than the children’s sum, increment it with the difference between the child nodes and the node.
- If the node is greater than the children’s sum, fix the node by either updating the left or the right subtree with the difference between the root and its children and then recursively fix the subtree.
- If the node is the same as the children’s sum, then do nothing.
Here’s a dry run of the algorithm on the above example.
1. Fix the left subtree.
2. Fix the right subtree.
3. Fix the root by updating the left child by the difference.
4. Fix the left subtree again.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include <iostream> #include <cmath> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Utility function to perform preorder traversal on a binary tree void preorder(Node* node) { if (node == nullptr) { return; } cout << node->data << ' '; preorder(node->left); preorder(node->right); } // Utility function to return the sum of the left and right children of a given node int findChildrenSum(Node* node) { int left = node->left ? node->left->data : 0; int right = node->right ? node->right->data : 0; return left + right; } // Function to fix a given binary tree to satisfy the children-sum property void fixBinaryTree(Node* root) { // base case: empty tree or leaf node if (!root || !root->left && !root->right) { return; } // recur for the left and right subtree fixBinaryTree(root->left); fixBinaryTree(root->right); // calculate the difference between the root and its children int diff = root->data - findChildrenSum(root); // if the root is less than the children's sum, increment it by `abs(diff)` if (diff < 0) { root->data += abs(diff); } // if the root is greater than the children's sum, fix the root by // either updating the left or right subtree by `diff` else if (diff > 0) { Node* subtree = root->left ? root->left : root->right; subtree->data += diff; fixBinaryTree(subtree); } } int main() { Node* root = new Node(25); root->left = new Node(8); root->right = new Node(10); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); fixBinaryTree(root); preorder(root); return 0; } |
Output:
25 12 7 5 13 6 7
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
// Data structure to store a binary tree node class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = this.right = null; } } class Main { // Utility function to perform preorder traversal on a binary tree public static void preorder(Node node) { if (node == null) { return; } System.out.print(node.data + " "); preorder(node.left); preorder(node.right); } // Utility function to return the sum of the left and right children of // a given node public static int findChildrenSum(Node node) { int left = node.left != null ? node.left.data : 0; int right = node.right != null ? node.right.data : 0; return left + right; } // Function to fix a given binary tree to satisfy the children-sum property public static void fixBinaryTree(Node root) { // base case: empty tree or leaf node if (root == null || root.left == null && root.right == null) { return; } // recur for the left and right subtree fixBinaryTree(root.left); fixBinaryTree(root.right); // calculate the difference between the root and its children int diff = root.data - findChildrenSum(root); // if the root is less than the children's sum, increment it by `abs(diff)` if (diff < 0) { root.data += Math.abs(diff); } // if the root is greater than the children's sum, fix the root by // either updating the left or right subtree by `diff` else if (diff > 0) { Node subtree = root.left != null ? root.left : root.right; subtree.data += diff; fixBinaryTree(subtree); } } public static void main(String[] args) { Node root = new Node(25); root.left = new Node(8); root.right = new Node(10); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); fixBinaryTree(root); preorder(root); } } |
Output:
25 12 7 5 13 6 7
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
# Data structure to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Utility function to perform preorder traversal on a binary tree def preorder(node): if node is None: return print(node.data, end=' ') preorder(node.left) preorder(node.right) # Utility function to return the sum of the left and right children of a given node def findChildrenSum(node): left = node.left.data if node.left else 0 right = node.right.data if node.right else 0 return left + right # Function to fix a given binary tree to satisfy the children-sum property def fixBinaryTree(root): # base case: empty tree or leaf node if root is None or root.left is None and root.right is None: return # recur for the left and right subtree fixBinaryTree(root.left) fixBinaryTree(root.right) # calculate the difference between the root and its children diff = root.data - findChildrenSum(root) # if the root is less than the children's sum, increment it by `abs(diff)` if diff < 0: root.data += abs(diff) # if the root is greater than the children's sum, fix the root by # either updating the left or right subtree by `diff` elif diff > 0: subtree = root.left if root.left else root.right subtree.data += diff fixBinaryTree(subtree) if __name__ == '__main__': root = Node(25) root.left = Node(8) root.right = Node(10) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) fixBinaryTree(root) preorder(root) |
Output:
25 12 7 5 13 6 7
The time complexity of the above solution is O(n2), where n is the total number of nodes in the binary tree. The auxiliary space required by the program is O(h) for the call stack, where h is the height of the tree. The worst case happens for a skewed tree whose nodes are in decreasing order from root to leaf.
2. Postorder Traversal
We can solve the problem in O(n) time. The idea is to fix the children-sum property for each node before processing its left and right subtree. After processing the left and right subtree, update the node again with the sum of the left and right child’s data.
The children-sum property can be fixed for a node by either updating the left or the right subtree with the difference between the root and its children. The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <iostream> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Utility function to perform preorder traversal on a binary tree void preorder(Node* node) { if (node == nullptr) { return; } cout << node->data << ' '; preorder(node->left); preorder(node->right); } // Function to fix a given binary tree to satisfy the children-sum property void fixBinaryTree(Node* root) { // base case: empty tree or leaf node if (!root || !root->left && !root->right) { return; } // calculate the difference between the root and its children int diff = root->data - ((root->left ? root->left->data : 0) + (root->right ? root->right->data : 0)); // if the root is greater than the children's sum, increment // either left or right child by `diff` if (diff > 0) { (root->left ? root->left : root->right)->data += diff; } // recur for the left and right subtree fixBinaryTree(root->left); fixBinaryTree(root->right); // update root with the sum of the left and right child's data root->data = (root->left ? root->left->data : 0) + (root->right ? root->right->data : 0); } int main() { Node* root = new Node(25); root->left = new Node(8); root->right = new Node(10); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); fixBinaryTree(root); preorder(root); return 0; } |
Output:
28 15 10 5 13 6 7
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
// Data structure to store a binary tree node class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = this.right = null; } } class Main { // Utility function to perform preorder traversal on a binary tree public static void preorder(Node node) { if (node == null) { return; } System.out.print(node.data + " "); preorder(node.left); preorder(node.right); } // Function to fix a given binary tree to satisfy the children-sum property public static void fixBinaryTree(Node root) { // base case: empty tree or leaf node if (root == null || root.left == null && root.right == null) { return; } // calculate the difference between the root and its children int diff = root.data - ((root.left != null ? root.left.data : 0) + (root.right != null ? root.right.data : 0)); // if the root is greater than the children's sum, increment // either left or right child by `diff` if (diff > 0) { (root.left != null ? root.left : root.right).data += diff; } // recur for the left and right subtree fixBinaryTree(root.left); fixBinaryTree(root.right); // update root with the sum of the left and right child's data root.data = (root.left != null ? root.left.data : 0) + (root.right != null ? root.right.data : 0); } public static void main(String[] args) { Node root = new Node(25); root.left = new Node(8); root.right = new Node(10); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); fixBinaryTree(root); preorder(root); } } |
Output:
28 15 10 5 13 6 7
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
# Data structure to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Utility function to perform preorder traversal on a binary tree def preorder(node): if node is None: return print(node.data, end=' ') preorder(node.left) preorder(node.right) # Function to fix a given binary tree to satisfy the children-sum property def fixBinaryTree(root): # base case: empty tree or leaf node if root is None or root.left is None and root.right is None: return # calculate the difference between the root and its children diff = root.data - ((root.left.data if root.left else 0) + (root.right.data if root.right else 0)) # if the root is greater than the children's sum, increment # either left or right child by `diff` if diff > 0: (root.left if root.left else root.right).data += diff # recur for the left and right subtree fixBinaryTree(root.left) fixBinaryTree(root.right) # update root with the sum of the left and right child's data root.data = (root.left.data if root.left else 0) + \ (root.right.data if root.right else 0) if __name__ == '__main__': root = Node(25) root.left = Node(8) root.right = Node(10) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) fixBinaryTree(root) preorder(root) |
Output:
28 15 10 5 13 6 7
The above solution works in linear time. Although the resulting tree satisfies the children-sum property, the difference of values in the resultant tree with the original tree is not necessarily minimal. The first approach, however, holds the children-sum property by adding minimal difference to the nodes.
Find difference between sum of all nodes present at odd and even levels in a binary tree
Fix a binary tree that is only one swap away from becoming a BST
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)