Hello friends!
And, welcome to another tutorial on GeeksforGeeks. In this video we are going to understand the
program which helps us in checking children sum property in a binary tree. First,
let us understand what exactly this property mean. According to this property, every node’s
data must be equal to the sum of data values in left and right children. Let us
see an example. As you can see, in this binary tree, we have
8+2=10 which is the parent node for nodes 8 and 2. Also, 3+5=8 ,which is the
parent node for nodes 3 and 5. And 2+0=2 which is the parent node of 2. Now, let
us look at the algorithm. Let us also have a sample tree to test our
algorithm. We pass the root node which is 10 into function
isSumProperty. So, node will point to 10. Also, we have two int variables left_data
and right_Data to store the data for left and right child. We initialize both of them
to 0. We check if node is null or a leaf node. Since
it is not, we move on to the else part. Now, we check if left child of node
exists and if it does, we assign left_Data variable to left child of node. Since left
child of node is equal to 8, left_data will now be equal to 8. We do the same thing for the right child.
SInce, the right child of node 10 is 2, right_Data will now be equal to 2. Now we check if node->Data is equal to
left_data+right_data. Since 8+2 is equal to 10 we now recursively call the left subtree
of node 10 using a call stack. We check is node is null, since it is not,
we move to the else part. Now, again the left_data and the right_data variables will
store the left and right child of node 8. So, left_Data will be equal to 3. And, right_Data will be equal to 5 Again, we check if node-data is equal to left_Data+right_Data.
Since, 5+3=8, it is true. We pass the left and right child of
node 8 now. The left child of 8 which is 3 is first passed. So, node will be equal to 3. NOw, we check if node is null or node is a
leaf node. Since 3 does not have both left and right child, it is a leaf node. So,
the first if condition is satisfied and we return 1. We continue execution for node 8. Now, we
pass the right child of node 8 which is 5. So node
will now point to 5. We check if 5 is null or 5 is a leaf node.
Since, node 5 does not have any child, it is a leaf node
and we return 1. Finally, we finish execution for node 8 and
since all three are true we return 1 We now move on to the right subtree of node
10. We pass the right child of node 10 which is
2.So, node will now point to 2. We check if two’s left child exist. Since
2’s left child is 2, Left_Data will now be equal to 2. Since the right child of two doesn’t exist,
right_Data remains 0. Now we check if node’s data is equal to
left_Data+right_data. Since 2+0=2, we continue. Now, the left child of 2 which is 2 is passed. We check if node is null or a leaf node. Since,
2’s left and right child are both null, it is a leaf
node and we return 1. Now we pass the right child of 2 which is
NULL. Since node is null, the first if condition
is satisfied and we return 1. Now, 1 will be returned to isSumProperty(10->Right)
as 1&&1&&1 is 1. Since 1&&1&&1 is equal to
1 we finally return 1 to the caller method. So, this tree holds children sum property.
Now, let us have a look at the time complexity of the
program. This code will run in O(n) complexity.Here
n are the number of nodes in our tree. With this we come to an end of this tutorial. For any doubts or suggestions please leave
them in the comment section below. Thanks for watching!