CODEWITHSUNDEEP
algorithm
Shlomi Kriheli
Shlomi Kriheli

Reputation: 340

Binary Tree - Algorithm that finds the number of leaves that are in even depth

The question is as follows:

Find an algorithm that gets a pointer to a binary tree (to the beginning of it) and returns the number of leaves that are in an even depth (level).

In this example, the algorithm will return 2 because we won't count the leaf in level 1 (since 1 is not even).

I guess I need a recursive algorithm. It's pretty easy if I pass two parameters I pass in the function (a pointer to a tree and level). I'm wondering if I can solve it with passing the pointer only, without the level.

Upvotes: 0

Views: 195

Answers (2)

user5745186
user5745186

Reputation:

You can, indeed, solve it using only one perimeter. However in that case, you need two little helper functions:

typedef struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int countForOdd(TreeNode*);
int countForEven(TreeNode*);
int count(TreeNode*);

//If the TreeNode to be passed as perimeter is at an odd level, call this function
int countForOdd(TreeNode *node)
{
    if(!node) return 0;
    return countForEven(node->left)
        + countForEven(node->right);
}
    //If the TreeNode to be passed as perimeter is at an even level, call this function
int countForEven(TreeNode *node)
{
    if(!node) return 0;
    return 1 + countForOdd(node->left)
        + countForOdd(node->right);
}

//And finally, our specific function for root is:
int count(TreeNode* root)
{
    return countForOdd(root);
}

Upvotes: 0

Monkey Supersonic
Monkey Supersonic

Reputation: 1254

Consider a function f which recursively descends in your tree. You have to differantiate three cases:

  1. Your current node has no children and its depth is even. You return 1.
  2. Your current node has no children and its depth is odd. You return 0.
  3. Your current node has children. You return the sum of all recursive calls of f on these children.

You have to define f on your own.

And no, it is not possible to define f with only one parameter. You have to memorize the current node as well as the actual depth. Recursive Algorithms, by their very nature, have no idea from where they are being called. You can, of course (but not recommended) remember the latter in a static variable as long as you do not parallelize f.

Also, you can "override" f that it takes only one paremeter and calls function f taking two parameters with the current depth set to 0.

Upvotes: 1

Related Questions