Sum of all leaf nodes of binary tree | GeeksforGeeks

Sum of all leaf nodes of binary tree | GeeksforGeeks


Hello friends!
And, welcome to another tutorial on GeeksforGeeks. In this video we are going to understand the
program which Finds the Sum of all leaf nodes of binary tree. FIrst, let us take an
example The idea is to traverse the tree in any fashion
and check if the node is the leaf node or not. If the node is the leaf node,
add node data to sum variable. Now, let us see the algorithm.
Let us also have a sample tree to test our algorithm.
We pass the root node which is 1 along with a sum variable which is initialized to
zero. Since root is not null, we check if root is
a leaf node. As the left and right children of ndoe 1 is not null, it is not a leaf node
and we pass the left child of 1 which is 2. Again as root is not null, we check if it
is a leaf node. As 2 is not a leaf node, we pass the left child of 2 which is 4.Hence,
root will now point to 4 As root is not null, we check if the left
and right of 4 is null. As it is true, we add
root’s data to sum. So, sum will now be equal to 4
Next, we pass the right child of 4 which is null. So, root will point to NULL.
As root is pointing to null, we return to the previous call.
Next, we pass the right child of 4 which is also null. So, root will again point to null.
As root is null, we return and finish execution for node 4
Execution for node 2 is resumed and now we pass the right child of 2 which is
null. So, root will point to null. As root is pointing to null, we return to
the previos call and finish execution for root
2. Execution for root=1 is resumed and now we
pass the right child of 1 which is 3. As root is not null, we check if 3 is a leaf
node. As the left and right of 3 is null, it is
a leaf node and we add it to sum. So, sum will now be equal to 7
The left and right of 3 is null so we return and finish execution for node 3.
Execution for node 1 is also over and we have the final sum which is 7.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!

Leave a Reply

Your email address will not be published. Required fields are marked *