Balance a Binary Search Tree | Simple Explanation | Leetcode 1382 | codestorywithMIK

Подписаться 59 тыс.

Просмотров 7 тыс.

50% 1

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

Опубликовано:

24 июн 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 79

@ankitrajpootr Месяц назад

Today is my Birthday🎉.

@venkatarohitpotnuru38 Месяц назад

happy birthday bro...

@codestorywithMIK Месяц назад

Wish you a very very Happy Birthday Ankit ❤️❤️❤️ Guys let’s all wish him and make his day 😇🎉🎊🎁🎈🎂

@AbhijeetMuneshwar Месяц назад

Happy Birthday, Ankit 🍰🎉

@varunpalsingh3822 Месяц назад

Happy Birthday bro, Enjoy your day 🎊🎉

@Himanshh_29 Месяц назад

Happy Birthday Ankit 🥳

@AbhijeetMuneshwar Месяц назад

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 ⚡

@codestorywithMIK Месяц назад

Means a lot ❤️🙏

@vishalkurve93 Месяц назад

@@codestorywithMIKReally sir you are helping us a lot🙌🙌🙌🥹

@gui-codes Месяц назад

Banda legend hai yaar. Itna determination chaie bas life me.

@meesalamahesheee_0056 Месяц назад

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?

@kaustubhchaudhari9838 Месяц назад

First shortest video of MIK bhai ever seen

@rajatrajgautam3224 Месяц назад

but bhai worth it h

@gui-codes Месяц назад

ha ha sahi baat. but video is gem as always.

@molyoxide8358 Месяц назад

Go see his shorts, even more shorter. Just joking buddy.

@adsnehi Месяц назад

I am not able to solve any daily challenge problem. but after watching 25% of you video I am able to solve it

@rohan8758 9 дней назад

Awesome explanation bhaiyan, You are like a angel to me who is leading me towards to crack FAANG or product based companies interview.

@user-ym1nv1pw8i Месяц назад

"Recursion leap of faith" . . . Thankyou sir!

@manasdeora4601 Месяц назад

Sir, you have been helping many like me understand the concepts in deep. Thankyou so much for your efforts.

@user-xe1tn9oy5d Месяц назад

short and crisp explanation thanks for this .

@raunakgiri5033 Месяц назад

It would be very helpful, if you also provide contest video solution, specially only problem D. Thanks.

@abhinaysahumusic6062 Месяц назад

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 !

@gauravbanerjee2898 Месяц назад

Thanks a lot bhaiya ❤❤

@CarWarYaar Месяц назад

Bhaiya aap bhot acha samjhate ho , dsa ke saare patterns pe koi video bana dijiye , question identify krne me problem hoti hai mostly

@bhuppidhamii Месяц назад

East ho ya West, MIK is best.

@priyanshkumariitd Месяц назад

Thank you bhaiya

@ReshuSharma-jc7yu Месяц назад

Bhaiya your segment tree playlist is awesome and looking forward for your backtracking and heap playlist

@dayashankarlakhotia4943 Месяц назад

Good explanation 👏 👍

@manojitsaha6262 Месяц назад

AVL Tree 🙂 Mujhe college ka kuch samajh nahi ata apke video se samjha ye concept acche se ❤❤❤

@aws_handles Месяц назад

Guruji 🙌🙏🏻

@aizad786iqbal Месяц назад

awesome

@gui-codes Месяц назад

MIK bhai zinda baad

@sabbyasachichakraborty1824 Месяц назад

LC 3193 kara do pls. Baaki jagah se samjh hi nhi aa rha. Count inversion wala

@rahulnegi4027 Месяц назад

us bro us

@focusman8801 Месяц назад

@codestorywithMIK Bhaiya please count inversion wala bana do

@user-do1eq7tl3e Месяц назад

yes please, male video on this.

@venkatarohitpotnuru38 Месяц назад

bhaiyya please do problems on partition dp

@codestorywithMIK Месяц назад

Soon planning in dp concepts playlist ❤️

@nish0798 Месяц назад

@@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

@venkatarohitpotnuru38 Месяц назад

@@codestorywithMIK Thank you bhaiyya..

@ropurifiedwater Месяц назад

@@codestorywithMIK thank you sir

@AdarshSingh-is6mg Месяц назад

bhaiya aap sheet recommend krskte ho koi for interview prep.

@jeehub041 Месяц назад

Sir jo new tree hum log construct kar rahe usko bhi toh space complexity me consider karenge na?

@__ankush_kushwaha Месяц назад

❤❤❤

@pokeindia5361 Месяц назад

Bhaiya please wo palindromic substringa ka blue print aapne diya tha uske variant karwao please..... Abhi placements aa rahe h

@rhydhamsingla9597 Месяц назад

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!

@Coder_Buzz07 Месяц назад

"College mein yeh problem karaya hoga" - college mein kuch nhi karata bhaiya sab khudse karte hai hum log😂😂

@kartikforwork Месяц назад

karwata hai na clg, maths, phy, chem, dip, human values, tecnical communication ... me time waste

@Coder_Buzz07 Месяц назад

@@kartikforwork 😂🤣🤣sahi bole bhai

@bhaktisharma9681 Месяц назад

Mujhe BST ki playlist he nahi mill rahi hai, koi pls share kar sakt hai uska link?

@Thriftinghai Месяц назад

Resursion ❌ Kahani (story) ✅

@yogeshchauhan9401 Месяц назад

In the if u are checking nums[idx]

@Rajdweep Месяц назад

man i didn't get the intuition for this

@dhairyachauhan6622 Месяц назад

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); } };

@theUnkown617 Месяц назад

arre bhaiya DSW bhi padha dete na 😭 me vohi padhne aya tha pr apne dokha de diya

@top_g755 Месяц назад

Sir segment tree plz

@mayank1522 Месяц назад

yaha par l > r kese hoga , l increase kese ho rha h ya r decrease kese ho rha

@yogeshchauhan9401 Месяц назад

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.

@piyush1394 Месяц назад

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); } };

@nish0798 Месяц назад

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]

@nish0798 Месяц назад

@codestorywithMIK please reply

@molyoxide8358 Месяц назад

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; } };

@ManojKrVerma-vw4dx Месяц назад

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); } };