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

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

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

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

[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 ⚡

[krunalkp]

Hi Mik you are really doing a great job you way of teaching is really nice, I code in python hence i watch your all video till the coding part and am able to do it by my self.

Thanks much recursion is indeed work magically.

Python Code :

class Solution:
def balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
arr = []
def inorder(root):
nonlocal arr
if root is None:
return
inorder(root.left)
arr.append(root.val)
inorder(root.right)
inorder(root)
def makebalance(left, right, arr):
if left > right:
return None
mid = left + (right - left) // 2
root = TreeNode(arr[mid])
root.left = makebalance(left, mid-1, arr)
root.right = makebalance(mid+1, right, arr)
return root
left = 0
right = len(arr) - 1
return makebalance(left, right, arr)

[adsnehi]

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

[kaustubhchaudhari]

First shortest video of MIK bhai ever seen

[Lakshya-fl]

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

[rohan]

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

[manasdeora]

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

[abhinaysahuu]

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 !

[manojitsaha]

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

[CarWarYaar]

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

[Abhishek-yij]

short and crisp explanation thanks for this .

[meesalamahesheee_]

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?

[raunakgiri]

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

[piyush]

class Solution {
public:
TreeNode* balancedTreeRoot(int l, int h, vector<int> &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<int> &vec){
if(root == nullptr) return;
createArray(root->left, vec);
vec.push_back(root->val);
createArray(root->right, vec);
}
TreeNode* balanceBST(TreeNode* root) {
vector<int> arr;
createArray(root, arr);
return balancedTreeRoot(0, arr.size()-1, arr);
}
};

[ReshuSharma-jcyu]

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

[dhairyachauhan]

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:

vector<int>inorder;

void fillInorder(TreeNode* root){
if(root == NULL){
return;
}
fillInorder(root->left);

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

}
};

[Coder_Buzz]

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

[pokeindia]

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

[venkatarohitpotnuru]

bhaiyya please do problems on partition dp

[AdarshSingh-ismg]

bhaiya aap sheet recommend krskte ho koi for interview prep.