Balance a Binary Search Tree | Simple Explanation | Leetcode 1382 | codestorywithMIK
Vložit
- čas přidán 24. 06. 2024
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 5th Video of our Playlist "Binary Search Tree : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve an extremely good problem : Balance a Binary Search Tree | Simple Explanation | Leetcode 1382 | 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 : Balance a Binary Search Tree | Simple Explanation | Leetcode 1382 | codestorywithMIK
Company Tags : Paytm
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/balance...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
In-Order Traversal:
Perform an in-order traversal of the given binary search tree (BST).
Store the values in a list to get a sorted sequence of elements.
Construct Balanced BST:
Use the sorted list to construct a balanced BST.
Recursively choose the middle element of the current subarray as the root to ensure the tree remains balanced.
Assign the left half of the list to the left subtree and the right half to the right subtree.
Rebuild the Tree:
Start the process from the entire range of the list (from 0 to the size of the list minus one).
The recursive construction ensures that the resulting tree is height-balanced.
Benefits:
The in-order traversal ensures that the elements are sorted, leveraging the properties of a BST.
Recursively choosing the middle element ensures the tree is as balanced as possible, minimizing the height.
✨ 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
Today is my Birthday🎉.
happy birthday bro...
Wish you a very very Happy Birthday Ankit ❤️❤️❤️
Guys let’s all wish him and make his day 😇🎉🎊🎁🎈🎂
Happy Birthday, Ankit 🍰🎉
Happy Birthday bro, Enjoy your day 🎊🎉
Happy Birthday Ankit 🥳
Respected MIK Sir,
Leetcode publishes new problem of the day at 5:30 AM daily.
You've published this video just after an hour.
Hats off to your dedication and efforts. 🙏🙇
You're an inspiration ⚡
Means a lot ❤️🙏
@@codestorywithMIKReally sir you are helping us a lot🙌🙌🙌🥹
Banda legend hai yaar.
Itna determination chaie bas life me.
I am not able to solve any daily challenge problem. but after watching 25% of you video I am able to solve it
Awesome explanation bhaiyan, You are like a angel to me who is leading me towards to crack FAANG or product based companies interview.
First shortest video of MIK bhai ever seen
but bhai worth it h
ha ha sahi baat. but video is gem as always.
Go see his shorts, even more shorter. Just joking buddy.
Sir, how did you gain so much knowledge and become consistent in DSA? What experiences and difficulties did you face during your initial stages in DSA, please tell?
"Recursion leap of faith"
.
.
.
Thankyou sir!
Sir, you have been helping many like me understand the concepts in deep. Thankyou so much for your efforts.
sir aapki explanations really the best h. mene ek striver ki binary tree ki video dekhi, smjh ni aaya code, aapki video dekhi, easily aa gya. please keep up the good work sir !
Bhaiya aap bhot acha samjhate ho , dsa ke saare patterns pe koi video bana dijiye , question identify krne me problem hoti hai mostly
It would be very helpful, if you also provide contest video solution, specially only problem D. Thanks.
short and crisp explanation thanks for this .
Thanks a lot bhaiya ❤❤
MIK bhai zinda baad
Thank you bhaiya
Good explanation 👏 👍
Bhaiya your segment tree playlist is awesome and looking forward for your backtracking and heap playlist
AVL Tree 🙂 Mujhe college ka kuch samajh nahi ata apke video se samjha ye concept acche se ❤❤❤
East ho ya West, MIK is best.
awesome
Guruji 🙌🙏🏻
bhaiyya please do problems on partition dp
Soon planning in dp concepts playlist ❤️
@@codestorywithMIK also please try to give tips how to be good at bottomup and when are u planning to do dp concepts and how amny videos estimated
@@codestorywithMIK Thank you bhaiyya..
@@codestorywithMIK thank you sir
❤❤❤
Bhaiya please make a separate video on DSW algorithm. I wanted to learn it and there is no video tutorial available. I checked those which were available, they don't explain any near to you. Please help!
bhaiya aap sheet recommend krskte ho koi for interview prep.
LC 3193 kara do pls. Baaki jagah se samjh hi nhi aa rha. Count inversion wala
us bro us
@codestorywithMIK Bhaiya please count inversion wala bana do
yes please, male video on this.
Bhaiya please wo palindromic substringa ka blue print aapne diya tha uske variant karwao please..... Abhi placements aa rahe h
Sir jo new tree hum log construct kar rahe usko bhi toh space complexity me consider karenge na?
man i didn't get the intuition for this
"College mein yeh problem karaya hoga" - college mein kuch nhi karata bhaiya sab khudse karte hai hum log😂😂
karwata hai na clg, maths, phy, chem, dip, human values, tecnical communication ... me time waste
@@kartikforwork 😂🤣🤣sahi bole bhai
In the if u are checking nums[idx]
This is how i did it.
was wondering, how to do it inplace, i know AVL TREE but never implement the rotation.
Even after being decent in recursion, it is difficult for me to implement it 😅
/**
* 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:
vectorinorder;
void fillInorder(TreeNode* root){
if(root == NULL){
return;
}
fillInorder(root->left);
inorder.push_back(root->val);
fillInorder(root->right);
}
TreeNode* makeTree(TreeNode*root,int start,int end){
if(start > end){
return NULL;
}
int mid = start + (end-start)/2;
TreeNode * node = new TreeNode(inorder[mid]);
node->left = makeTree(root,start,mid-1);
node->right = makeTree(root,mid+1,end);
return node;
}
TreeNode* balanceBST(TreeNode* root) {
fillInorder(root);
return makeTree(root,0,inorder.size()-1);
}
};
arre bhaiya DSW bhi padha dete na 😭 me vohi padhne aya tha pr apne dokha de diya
Resursion ❌
Kahani (story) ✅
Mujhe BST ki playlist he nahi mill rahi hai, koi pls share kar sakt hai uska link?
Sir segment tree plz
yaha par l > r kese hoga , l increase kese ho rha h ya r decrease kese ho rha
We are recursively passing them in the function like for left subtree construct(l,mid-1) and for right subtree(mid+1,r)
and as a base case we are checking is l>r that means there is no more element to process so we return NULL.
public int subarraySum(int[] nums, int k) {
// Call the helper function with an initial sum of 0
return helper(nums, k, 0);
}
private int helper(int[] nums, int k, int idx) {
if(idx>=nums.length)
{
if(k==0)
{
return 1;
}
return 0;
}
int take=0;
if(nums[idx]
@codestorywithMIK please reply
class Solution {
public:
TreeNode* balancedTreeRoot(int l, int h, vector &arr){
if(l > h){
return NULL;
}
int mid = l + (h-l)/2;
TreeNode* root = new TreeNode(arr[mid]);
root->left = balancedTreeRoot(l, mid-1, arr);
root->right = balancedTreeRoot(mid+1, h, arr);
return root;
}
void createArray(TreeNode* root, vector &vec){
if(root == nullptr) return;
createArray(root->left, vec);
vec.push_back(root->val);
createArray(root->right, vec);
}
TreeNode* balanceBST(TreeNode* root) {
vector arr;
createArray(root, arr);
return balancedTreeRoot(0,arr.size()-1, arr);
}
};
Bro my code is not running pls help me:
class Solution {
public:
int n = 0;
vector arr;
TreeNode* newRoot = NULL;
TreeNode* temp = NULL;
void SolveLeft(int l, int r, vector &arr)
{
if(lleft = new TreeNode(arr[mid]);
temp = temp->left;
SolveLeft(l, mid-1, arr);
}
}
void SolveRight(int l, int r, vector &arr)
{
if(lright = new TreeNode(arr[mid]);
temp = temp->right;
SolveRight(mid+1, n-1, arr);
}
}
void Inorder(TreeNode* root)
{
if(root != NULL)
{
Inorder(root->left);
arr.push_back(root->val);
Inorder(root->right);
}
}
TreeNode* balanceBST(TreeNode* root) {
Inorder(root);
n = size(arr);
int mid = (0+n-1)/2;
newRoot = new TreeNode(arr[mid]);
temp = newRoot;
SolveLeft(0, mid-1, arr);
temp = newRoot;
SolveRight(mid+1, n-1, arr);
return newRoot;
}
};
What is the issue with this code ?
/**
* 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:
void helper(TreeNode* root, vector &sorted) {
if (root == NULL) return;
helper(root->left, sorted);
sorted.push_back(root);
helper(root->right, sorted);
}
TreeNode* balancedBST(vector sorted, int l, int h) {
if (l > h)
return NULL;
if (l==h){
return sorted[l];
}
int m = (h+l) / 2;
TreeNode* root = sorted[m];
root->left = balancedBST(sorted, l, m - 1);
root->right = balancedBST(sorted, m + 1, h);
return root;
}
TreeNode* balanceBST(TreeNode* root) {
// first get sorted vector
vector sorted;
helper(root, sorted);
//return NULL;
return balancedBST(sorted, 0, sorted.size()-1);
}
};