0

I am trying to learn as much as i can about tree's and their algorithm's. And it seems like i can't really learn how recursion works when i want to count something in binary tree. For example if i want to count nodes or leaves or something else. When i look in the solution i don't get it how counter increases and so on.I can remember solution for that particular problem but, when i get another problem which includes counting i dont know how to start my function.

Do you have any advice about my problem ? How did you learn different counting algorithms with recursion. I perfectly understand every iterative solution and i know how to use it .

Thanks in advance for your response

Miljan Rakita
  • 1,433
  • 4
  • 23
  • 44
  • 1
    Possible duplicate of [Understanding recursion](http://stackoverflow.com/questions/717725/understanding-recursion) –  Dec 09 '16 at 00:30
  • 1
    Well, a good point to start off would be to understand the recursive definition of trees (mentioned on [wikipedia](https://en.wikipedia.org/wiki/Binary_tree) for example). From that point onwards the rest is pretty straightforward. –  Dec 09 '16 at 00:31
  • @Paul That link helped a bit but, my main problem is counting something with recursion not just recursion like he mentioned. Thanks for the link – Miljan Rakita Dec 09 '16 at 00:34

2 Answers2

0

For counting something in a binary tree, its recursive definition comes in quite handy:

A tree consists of three elements: a node N which is the root, the subtree L, which is a tree itself and the subtree R, which is a tree as well.

Using this definition, we can for example count the leaves of a tree in the following manner:
The number of leaves of a tree is

  • 0 if the tree is empty (N is null)
  • 1 if both L and R are empty
  • the number of leaves in L and R otherwise

The basic idea is that we can use the property that a leave has no children (both L and R are empty) and the fact that an empty tree has no leaves as base case. From that point we can simply say a tree has either one of the above properties and thus the root itself is a leave or there are no nodes in the tree, or the leaves are distributed over L and R, and we simply need to count and sum up the number of leaves in both subtrees.

Or as pseudocode:

countLeaves(node N):
    //the tree is empty
    if N == null:
        return 0

    //N is a leave
    if L == null && R == null:
        return 1

    //count leaves in both subtrees
    return countLeaves(L) + countLeaves(R)
  • Well i don't want to focus only on this problem, i mentioned it as example. My problem are algorithms which include counting with recursion. But this is really clear and good example of counting. Thanks – Miljan Rakita Dec 09 '16 at 01:46
  • @MiljanRakita this is a demonstration of the basic pattern that is used to count recursively in a tree. It can be altered to work for pretty much any counting-problem with binary trees (or to go one step further even with k-ary trees). –  Dec 09 '16 at 01:52
  • Check this code: http://pastebin.com/JUVnRL8p i tried to count nonLeaves with this method and it doesn't work. That is what i say i can learn about one particular problem, but get stuck when i try to solve something similar. – Miljan Rakita Dec 09 '16 at 02:02
  • @MiljanRakita try to create a reasoning likewise to what I did in the example: Consider how to handle the empty tree, how to handle nodes that don't meet a specific requirement (e.g. in your case the node is a leave) and how to handle the most general tree where `L` and `R` are not empty. For example: the number of non-leaves in a tree is 1 + the number of leaves in `L` and `R` summed up, unless the tree is empty or `N` is a leave. You need to derive the logic first and afterwards work on the actual implementation. –  Dec 09 '16 at 02:16
  • thank you a lot. I went through many of examples and i think i am getting better a this. Thank you for help ! – Miljan Rakita Dec 09 '16 at 02:40
  • @MiljanRakita glad to help :) –  Dec 09 '16 at 02:57
0

Many people face difficulty in counting in trees using recursion (or in general with recursive solutions). So I will give suggestions without taking any particular example.

Problem with tree and recursion is - the flow of control in not straight forward like iterative solutions. In tree you have to visit all branches and in particular all the nodes and based on the demand of the problem count something. Whatever traversal you use, you need to figure out first what is the condition for any node to be counted, like if you are looking for leaves then what condition defines any node - a leaf. Once you figure it out, you get the acknowledgement of base condition in your recursion and then you can just keep visiting every node, increase counter on meeting that particular condition and terminate or return from recursive calls on meeting returning/terminating conditions.

You need to train your mind a bit to visualise the recursive structure, and for that just do manual run of recursive functions for the problems you read or memorised. Do it for few problems with your created examples. Hope it helps!

CNatka
  • 48
  • 1
  • 5