CODEWITHSUNDEEP
pythonpython-3.xbinary-search-treenodes
generation_coding
generation_coding

Reputation: 53

How would you calculate the sum of a binary tree recursively with given input tree?

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.

enter image description here

def sum(t: TN) -> int:
    if t == None:
        return 0
    else:
       return [sum(t.value)for v in t]

Upvotes: 1

Views: 2671

Answers (1)

BlueJapan
BlueJapan

Reputation: 1766

1.What we have here:

  • Given the root of tree.
  • Find the sum of the whole tree.
  • Using recursive.

    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.

  • We need a base, which will terminate the recursive function, otherwise it will infinite loop.
  • Once we have base case, now we need to start execution of rest.

    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

    • Related Questions