Reputation: 53
Hi! I need help finding a way to calculate the sum of a binary tree recursively. I have put what I have been working on but I am still really confused. Please, any help would be appreciated.
Define a recursive function named sum, which takes a binary tree as an argument, and returns an int – the sum of all the node values in the tree. For the tree on bottom for example, the function returns 35.
def sum(t: TN) -> int:
if t == None:
return 0
else:
return [sum(t.value)for v in t]
Upvotes: 1
Views: 2671
Reputation: 1766
1.What we have here:
2.Recall what is recursive?
A recursive function is a function that calls itself during its execution. This enables the function to repeat itself several times, outputting the result and the end of each iteration
3.
4.
For a Binary Tree, it has root, (optional) left child, (optional) right child. We can choose root as a base case, because this is the start point of a binary tree.
private int sum(TreeNode root) {
//1. base case
if(root == null){
return 0;
}
//2. go bigger
else {
return root.val + sum(root.left) + sum(root.right);
}
}
Upvotes: 1