Even Odd Tree | DFS | BFS | Leetcode 1609

Показать описание

This is the 42nd Video of our Playlist "Binary Tree : Popular Interview Problems".
In this video we will try to solve a very good Binary Tree problem : Even Odd Tree | Leetcode 1609

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Even Odd Tree | DFS | BFS | Leetcode 1609
Company Tags : AMAZON

Approach Summary :
Approach-1 (BFS)
Algorithm:
Uses Breadth-First Search (BFS) to traverse the tree level by level.
Maintains a queue to keep track of nodes at each level.
Uses a boolean flag (even_level) to alternate between even and odd levels.
Checks if values in even levels are strictly increasing and odd levels are strictly decreasing.
Complexity:
Time Complexity: O(n) - where n is the number of nodes in the tree.
Space Complexity: O(n) - in the worst case, when the queue stores all nodes at the maximum level.
Approach-2 (DFS)
Algorithm:
Uses Depth-First Search (DFS) with a recursive approach.
Maintains a vector (levelPrev) to store the previous value at each level.
Checks if values at even levels are strictly increasing and odd levels are strictly decreasing.
Complexity:
Time Complexity: O(n) - where n is the number of nodes in the tree.
Space Complexity: O(n) - uses additional space for the vector levelPrev and recursion stack. The recursion depth is determined by the height of the tree.
These approaches aim to determine if a given binary tree is an Even-Odd Tree based on specific rules about the values in even and odd levels. The BFS approach uses a queue for level-order traversal, while the DFS approach utilizes recursive calls and a vector to track previous values at each level. Both approaches have a time complexity of O(n) but differ in their space complexity.

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

✨ Timelines✨
00:00 - Introduction
02:28 - Approach 1 BFS
11:40 - Coding Approach 1
16:01 - Time & Space
16:18 - Approach 2 DFS
33:43 - Coding Approach 2
38:39- Time & Space

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024

codestorywithMIK

Комментарии

Leetcode should select you as the tutor 🤠

thefinalfit

Sir you are not a good teacher rather than you are an excelent teacher.I seen your video first time.

AmitYadav-lodv

Dfs solution you making easy to understand
And
36:00
Level%2==root->val. ===-> comparison operator

PradipLabade-oo

Bhai Congratulations for ~28K Subscribers its few days back we just 19K fam and its increasing rapidly now everyone get to know the quality of your content Lots of Love❤

Kode_with_Kushwah

DFS solutions are always interesting in these types of problems

sauravchandra

Why is the time complexity O(n2) (meant to write n square)? O(n) time for every time we resize and it will be called for "max depth of the tree" number of times. In a skewed tree depth would be same as number of nodes. So is that why we have O(n2)? Have I understood this correctly?

soumyasatish

please make videos of daily GFG problems as well

parthbhatti

could code the DFS after listening to that one click point "baad mei bhi use hoga kabhi",

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:

def custom_default():
return None
lot = defaultdict(custom_default)
res = True
def helper(node, level) :
nonlocal lot, res
if node :
left = helper(node.left, level + 1)
right = helper(node.right, level + 1)

if level % 2 == 0 :
if node.val % 2 == 0 or (lot[level]!= None and lot[level] >= node.val) :
res = False
else:
if node.val % 2 == 1 or (lot[level]!= None and lot[level] <= node.val) :
res = False
lot[level] = node.val
helper(root, 0)
return res

ArjunSaxena-wlqs

DFS approach boht mast tha bhaiya !! 🤩🤯
Here is my code, mene array ke badle, map use kra hai

class Solution {
public:
bool f(TreeNode* root, int level, unordered_map<int, int>& m) {

if (root == NULL) {
return true;
}

if (m.find(level) == m.end()) {

if (level % 2 == 0 && root->val % 2 == 0)
return false;
if (level % 2 == 1 && root->val % 2 == 1)
return false;

m[level] = root->val;
}

else {

int prev = m[level];

if (level % 2 == 0 && (prev >= root->val || root->val % 2 == 0)) {
return false;
}
if (level % 2 == 1 && (prev <= root->val || root->val % 2 == 1))
return false;

m[level] = root->val;
}

return f(root->left, level + 1, m) && f(root->right, level + 1, m);
}

public:
bool isEvenOddTree(TreeNode* root) {

unordered_map<int, int> m;
// level, element

return f(root, 0, m);
}
};

anshumaan

class Solution {
public:
bool isEvenOddTree(TreeNode* root) {
if(!root) return false;
queue<TreeNode*> q;
bool level = false; // false -> even and true -> odd
q.push(root);
while(!q.empty()){
int n = q.size();
int val_even = INT_MIN;
int val_odd = INT_MAX;
while(n--){
TreeNode *node = q.front();
q.pop();
if(level == false && node != NULL){
if(node->val % 2 == 0) return false;
if(val_even >= node->val) return false;
q.push(node->left);
q.push(node->right);
val_even = node->val;
}
if(level == true && node != NULL){
if(node->val % 2 != 0) return false;
if(val_odd <= node->val) return false;
q.push(node->left);
q.push(node->right);
val_odd = node->val;
}
}
level = !level;
}
return true;
}
}; ❤❤

utkarshsahay

instead of resizing every time we can take a large sized array

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> arr;
bool solve(TreeNode* root, int level){
if(root==NULL) return true;
int val = root->val;
bool curr = ((level & 1) ? ((val%2==0) && (val<arr[level])) : ((val%2==1) && (val>arr[level])));
arr[level] = val;
return curr && solve(root->left, level+1) && solve(root->right, level+1);
}
bool isEvenOddTree(TreeNode* root) {
arr.resize(1e5+1, -1);
for(int i=0; i<=1e5; i++){
if(i&1){
arr[i] = 1e9;
}else{
arr[i] = -1e9;
}
}
return solve(root, 0);
}
};

iWontFakeIt

class Solution {
public:
using Node = TreeNode;
bool isEvenOddTree(TreeNode* root) {

queue<Node*> q;

q.push(root);
bool parity = 0;
while(!q.empty())
{
int size = q.size();
parity = !parity;
int prev;
prev = (parity==0 ? 1e6+1:-1);

for(int i = 0 ; i < size ; i++)
{
Node *temp = q.front() ; q.pop();
if(temp->left) q.push(temp->left);
if(temp->right) q.push(temp->right);
if(parity == 0)
{
if((temp->val) %2 !=0 || prev <= temp->val)
{ return 0;}
}
else
{
if((temp->val) %2 !=1 || prev >= temp->val)
return 0;

}
prev = temp->val;
}
}

return 1;

}
};

class Solution {
public:
using Node = TreeNode;
bool check(Node *root, int lvl, vector<int> &vec)
{
if(root == 0)
return 1;

if(lvl%2 == 0)
{
if( (root->val)%2 == 0 ) return 0;
if(vec[lvl]!=-1 && vec[lvl] >= root->val)
return 0;
}
else
{
if( (root->val)%2 == 1 ) return 0;
if(vec[lvl]!=-1 && vec[lvl] <= root->val)
return 0;

}
vec[lvl] = root->val;

return check(root->left, lvl+1, vec) && check(root->right, lvl+1, vec);
}
bool isEvenOddTree(TreeNode* root) {

if(root == 0)
return 1;

vector<int> vec(1e5, -1);
return check(root, 0, vec);

}
};

tusharnanda

//DFS -> unordered_map to store prev value

unordered_map<int, int> levelValue;
bool dfs (TreeNode* root, int level){
if (root == NULL){
return true;
}
if (level % 2 == root->val % 2)//if (odd == odd or even == even)
return false;

if (levelValue.find(level) != levelValue.end()){
int prevValue = levelValue[level];
//even -> odd increasing
if (level % 2 == 0 && root->val <= prevValue || level % 2 != 0 && root->val >= prevValue) {
return false;
}
}
levelValue[level] = root->val;
return dfs(root->left, level+1) && dfs(root->right, level+1);
}

theOmKumar

public boolean isEvenOddTree(TreeNode root){
Queue<TreeNode>q=new
boolean evenLevel=true;
for(;!q.isEmpty();evenLevel =!evenLevel){
int
for(int sz=q.size();sz>0;sz--){
TreeNode cur=q.poll();
if((evenLevel&&(cur.val
return false;
}
prev=cur.val;
if(cur.left!=null)
q.offer(cur.left);
if(cur.right!=null)
q.offer(cur.right);
}
}
return true;
}
🎉❤

dayashankarlakhotia