Minimum Height Trees | Know Every Detail | Why BFS | GOOGLE | Leetcode 310 | codestorywithMIK
347Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 48th Video of our Playlist "Graphs : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very good and famous Graph BFS problem : Minimum Height Trees | Know Every Detail | Why BFS | GOOGLE | Leetcode 310 | 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 : Minimum Height Trees | Know Every Detail | Why BFS | GOOGLE | Leetcode 310 | codestorywithMIK
Company Tags : GOOGLE
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Topological%20Sorting/Minimum%20Height%20Trees.cpp
Leetcode Link : https://leetcode.com/problems/minimum-height-trees/
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Approach Summary :
The approach aims to find the minimum height trees in a given undirected graph represented by its nodes and edges. It does so by iteratively removing leaf nodes (nodes with only one neighbor) until there are at most two remaining nodes, which would be the root nodes of the minimum height trees. The key steps involved are:
1. Constructing an adjacency list to represent the graph and calculating the indegree of each node.
2. Enqueuing all leaf nodes (nodes with indegree 1) into a queue.
3. Iteratively dequeuing leaf nodes and reducing the indegree of their neighbors.
4. Removing the dequeued nodes and their adjacent edges from the graph.
5. Repeating steps 2-4 until there are at most two nodes left in the graph.
6. Returning the remaining nodes, which represent the roots of the minimum height trees.
This approach efficiently identifies the nodes that form the roots of the minimum height trees by gradually trimming the graph from its outermost layers towards its core.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
00:19 - Problem Explanation
06:02 - Brute Force
13:02 - Optimal
40:10 - Coding it up
#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