hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Level Leaf
Problem : Level Leaf
Problem Link : www.codingninjas.com/codestudio/problems/level-leaf_3210614
Companies Asked : Amazon, FlipKart
Approach:
We will start traversing through the nodes.
While moving ahead if we find a node that does not have any left or right child, that means we are standing at a leaf node.
Now for that node check level.
If the level matched with an already calculated level then return true. Else return false.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(1)
Code [C++]
#include <bits/stdc++.h>
/************************************************************
Following is the TreeNode class structure:
template <typename T>
class TreeNode {
public:
T data;
TreeNode<T> *left;
TreeNode<T> *right;
TreeNode(T data) {
this->data = data;
left = NULL;
right = NULL;
}
};
************************************************************/
bool solve(TreeNode<int> *root, int cnt, int & lvl){
if(!root) return 1;
if(!root->left && !root->right){
if(lvl == -1) lvl = cnt;
return lvl == cnt;
}
return solve(root->left, cnt + 1, lvl) & solve(root->right, cnt + 1, lvl);
}
int levelLeaf(TreeNode<int> *root, int cnt = 0) {
int lvl = -1;
return solve(root, 0, lvl);
}