Number of Good Leaf Nodes Pairs | Using Graph And BFS | Dry Run | Leetcode 1530 | codestorywithMIK

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

This is the 47th Video of our Playlist "BINARY TREE : Popular Interview Problems" by codestorywithMIK

In this video we will try to solve a very good Tree Problem : Number of Good Leaf Nodes Pairs | Using Graph And BFS | Dry Run | Leetcode 1530 | codestorywithMIK

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 : Number of Good Leaf Nodes Pairs | Using Graph And BFS | Dry Run | Leetcode 1530 | codestorywithMIK
Company Tags : Will update soon

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

Summary :
The key methods are makeGraph and countPairs.

Converts a binary tree into an undirected graph using an adjacency list (adj).
Marks leaf nodes by adding them to a set (st).
Takes root as the current node, prev as the previous node, and recursively processes the tree.
If the current node (root) is a leaf node, it is added to the set of leaves.
Connects the current node with its parent (prev) in the adjacency list.
*countPairs(TreeNode root, int distance)**:

Initializes an adjacency list (adj) and a set of leaf nodes (st).
Calls makeGraph to populate these structures.
Uses BFS (Breadth-First Search) to find pairs of leaf nodes within the specified distance.
For each leaf node, it performs BFS up to the given distance, checking if other leaf nodes are reachable within this distance.
Counts and returns the number of valid leaf node pairs, dividing by 2 to avoid double-counting.

✨ Timelines✨
00:00 - Introduction

#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

Рекомендации по теме

Комментарии

Bhaiya aapke jaisa koi Nahi .. ur change DSA industry 😍😍😍😍😍🥰🥰🥰🥰😘😘

GateDA-omkarpunjaji

Yes, Bhaya We want a video on the second approach.

goosebumps

bhiya apki wajah se bhot help mil rahi hai plz dp ki full playlist banana suru karo

jatinsharma

thankyou men
i also thought the same approach but not thought about using graph

chad._life

Brute force solution can be to write the path from root to leaf for all leaves and deduce the lca for one leaf by looking for the closest common node in all other leaf paths . Tc n*n for all path traversals space n*n for storing all paths .

visheshtiwari

Thanks a lot. After doing Graph Concepts playlist, I feel very confident in problems like these where we have to apply BFS or DFS.
When you get time this weekend or tomorrow, please post video on 2nd Approach as well.
Thank you

gui-codes

Yes i want 2nd Solution. Today i have made the same solution, but somehow couldn't pass the all testcases. thank you mik for helping us.

spdh

Using LCA inorder to find the smallest distance between two leaf nodes.

AjinkyaJagtap-js

Yes, we would like to learn second optimum approach too ⚡

AbhijeetMuneshwar

Yes bro please upload the second approach video also. Thanks a lot.

playwithlinux

One more approach would be to create paths to leaf nodes (DFS) and loop over them to find distances. This approach would restrict memory of a graph, but requires memory to store paths of leaf nodes from root. Still space complexity and time complexity both would be O(n²). 😢

SriHarshaChilakapati

Yeaah!! Please share the another video with another approach.

soumyajain

I have used Lowest common Ancestor approach by first finding path string then comparing them with every other leaf node path.

class Solution {
bool goodLeaf(string&str1, string&str2, int&distance){
int n=min(str1.size(), str2.size());
int i=0;
for(;i<n;i++){
if(str1[i]!=str2[i])break;
}
int len1=str1.size()-i;
int len2=str2.size()-i;
return (len1+len2)<=distance;
}
void f(TreeNode*root, vector<string>&path, string&temp){
if(root==NULL){
return;
}
if(root->left!=NULL){
temp.push_back('L');
f(root->left, path, temp);
temp.pop_back();
}
if(root->right!=NULL){
temp.push_back('R');
f(root->right, path, temp);
temp.pop_back();
}

return;
}
public:
int countPairs(TreeNode* root, int distance) {
vector<string>path;
string temp="";
f(root, path, temp);
int ret=0;
for(int i=0;i<path.size();i++){
for(int j=i+1;j<path.size();j++){
if(goodLeaf(path[i], path[j], distance))ret++;
}
}

return ret;
}
};

AdarshSingh-ismg

I coded the map plus recursion leap of faith solution. hen1 and hen2 store the distance of leaves from the node. we use the information to compute the final result.

class Solution {
public:
int countPairs(TreeNode* root, int distance) {
if (root == NULL) {
return 0;
}
int rig = countPairs(root->right, distance);
int lef = countPairs(root->left, distance);
unordered_map<int, int> hen1;
solve(hen1, root->left, 1);
unordered_map<int, int> hen2;
solve(hen2, root->right, 1);
int ans = rig + lef;
for (int i = 1; i < distance; i++) {
for (int j = 1; j + i <= distance; j++)
ans += hen1[i] * hen2[j];
}
return ans;
}
void solve(unordered_map<int, int>& hen, TreeNode* root, int level) {
if (root == NULL) {
return;
}
if (root->right) {
solve(hen, root->right, level + 1);
}
if (root->left) {
solve(hen, root->left, level + 1);
}
if (root->right == NULL && root->left == NULL) {
hen[level]++;
return;
}
}

madhavdikshit