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 to the left below does not hold the children-sum property. It should be converted to a binary tree to the right that has that property.
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.
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
|
#include <iostream>
#include <cmath>
using namespace std;
// 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 & right children of a given node
int children_sum(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 – children_sum(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
|
// 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 & right children of a given node
public static int children_sum(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 – children_sum(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
|
# 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 & right children of a given node
def children_sum(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 – children_sum(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
Download Run Code
Output:
25 12 7 5 13 6 7
Download Run Code
Output:
25 12 7 5 13 6 7
Download Run Code
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 used 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.
We can solve the problem in O(1) 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
|
#include <iostream>
using namespace std;
// 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->data + root->right->data);
// 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->data + root->right->data);
}
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
|
// 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.data + root.right.data);
// 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.data + root.right.data);
}
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
|
# 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 + root.right.data)
# 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 + root.right.data)
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
Download Run Code
Output:
28 15 10 5 13 6 7
Download Run Code
Output:
28 15 10 5 13 6 7
Download Run Code
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 the minimal difference to the nodes.
source