Recover a Tree From Preorder Traversal | Easy DFS Simulation | Leetcode 1028 | codestorywithMIK

Hi Everyone, this is the 56th video of our Playlist "Binary Tree : Popular Interview Problems".
Now we will be solving a good String problem - Recover a Tree From Preorder Traversal | Easy DFS Simulation | Leetcode 1028 | codestorywithMIK

Problem Name : Recover a Tree From Preorder Traversal | Easy DFS Simulation | Leetcode 1028 | codestorywithMIK
Company Tags : Will update later

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

Video Summary :
The solution reconstructs a binary tree from a preorder traversal string by parsing node depths using dashes. It recursively extracts values, builds nodes at the correct depth, and maintains position tracking with an index array. This ensures proper tree structure while preserving preorder order.

✨ Timelines✨
00:00 - Introduction
00:31 - Motivation
00:41 - Problem Explanation
03:26 - Thought Process and Simulation
16:13 - Story To Code
19:24 - Most Important Point
23:00 - Coding it up

#MIK #mik #Mik
#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 #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[codestorywithMIK]

19:14 Small correction - depth increases by 1
Apologies for the delay today. I hurt my leg while playing basketball 🏀 🙂
On a bed rest today.

Hope you all understand ❤️🙏😇

[xturbo.]

hi bhaiya ajj paytm me mera selection ho gya apki wajah se all thanks to you

[GauravDuseja-tq]

I got placement in western union thanku very much ❤🙏

[ankurbhambri]

I liked this quote - `You can never change your life without first changing your daily habits. True success lies in the consistency of your everyday routine.`

[gui-codes]

Take bed rest bhaiya.
And no doubt you are the best tutor I have ever seen in my life

[shwetabh-]

I finally got an internship today, your videos and motivational quotes have been a real help, thank you mik.

[monaagrawal]

I initially had trouble understanding the question, but after watching the first four minutes of your video, it became clear. I was then able to complete it on my own, though it took me approximately 1.5 hours.

Thank you for your videos—because of them, I have been dedicatedly completing LeetCode daily. Here is my approach to solving this question. This is my first comment on your video, though I’ve been watching them for the past 20–25 days. I hope you’ll read it! The reason for my comment is that I’m really happy to have completed a hard Tree question on my own.



class Pair
{
TreeNode node;
int d;
Pair(TreeNode node, int d)
{
this.node=node;
this.d=d;
}
}
class Solution {
public TreeNode recoverFromPreorder(String t) {

Stack<Pair> st=new Stack<>();

int i=0;
int j=0;
int d=0;
int number=0;

int n=t.length();

TreeNode root=null;
TreeNode node=root;



for(j=0 ;j<t.length();)
{
if(t.charAt(j)!='-')
{
d=j-i;

number=0;
while(j<n && t.charAt(j)!='-')
{

j++;
}

if(st.isEmpty() || d==0)
{
root=new TreeNode(number);
node=root;
}

else if(!st.isEmpty() && d-1==st.peek().d)
{
node.left=new TreeNode(number);
node=node.left;

}else {
while(!st.isEmpty() && d<=st.peek().d) st.pop();


if(!st.isEmpty()){
node=st.peek().node;
node.right=new TreeNode(number);
node=node.right;
}

}

st.push(new Pair(node, d));
i=j;
continue;

}
j++;
}
return root;

}
}

[vishwashsoni]

bhaiyaaa aap k wajha se aaj ka hard question khud se ban gaya mujhe thoda time laga around 1.5 hrs but ban gaya finally!!!! and Sad to hear that you got injured while playing. Get well soon! ❤

this is how i solved this problem :

class Solution {
public:
TreeNode* makeTree(string& traversal, int& i, int level) {
if (i >= traversal.size()) {
// matlab string khatam hai aage koi node nahi to NULL return kardo
return nullptr;
}

int countDash = 0;
while (i < traversal.size() && traversal[i] == '-') {
countDash++; //... Number of dash calculate karlo
i++;
}

if (countDash != level) {
//... agar is level k equal nahi hai Dash to ye node kisi or level ka hoga
//... i ko fir se apne initial position pe kado or NULL return kardo
i -= countDash;
return nullptr;
}

int num =0; // agar level k equal hai Dashcount to matlab sahi level pe hai
// or yaha k left and right child ko value assign kardo

while (i < traversal.size() && traversal[i] != '-') {
num = (num * 10) + (traversal[i] - '0'); //... make value from string
i++;
}

TreeNode* root =
new TreeNode(num); //... present node ko value assign kardo

root->left = makeTree(traversal, i, level + 1); //... left child pe leap of faith
root->right = makeTree(traversal, i, level + 1); //... right child pe leap of faith

return root; //... root ans return kardo
}
TreeNode* recoverFromPreorder(string traversal) {
int n = traversal.size();
int i = 0;
return makeTree(traversal, i, 0);
}
};

[ayushsonkar]

i was just waiting for your video sir, thank you

[shatranjKaKamaal]

Take care MIK, thank you for such a wonderful explanation!

[harshkankariya]

Thanks Mik for Motivating us to solve daily potd!

[FanIQQuiz]

I also like basketball .
And take bed rest MIK
Hats off to your dedication ❤️

[HB_Dhakad]

I got placed in TCS Digital Thank you bhaiya and my dream is Microsoft if you motivate me than i definatly got it .

[SonuKumar-cwrg]

Today I am able to solve this problem by myself using iterative approach

[aniruddhakotal]

Hey, In the explanation part, you have taken depth + 2, in recursion call, and I was totally confused, why.. But then in code, you have written the correct one. Great solution..

[Babysitter-dy]

Bhaiya agar aapka video aane mein zara sa bhi late ho jata hn toh mujhe dar lagne lagta hn😅...Thanks bhaiya for this video❤

[AbhijeetMuneshwar]

Respected MIK Sir,

You've posted this video despite being injured.
Hats off to your dedication.

Please have rest 🙏

[aryansinha]

Take care Bhaiya, I pray for your speedy recovery.

[supratickmondal]

Cracked Microsoft thanks guruji made my logics stronger day by day 🤗🤗

[SinghalRishi]

Bhaiya i did it like this its a swift solution but you will understand this

class Solution {
var arr = [(num: Int, dash: Int)]()
var i = 0

func recoverFromPreorder(_ traversal: String) -> TreeNode? {
processInput(traversal)
return buildTree(0)
}

func buildTree(_ depth: Int) -> TreeNode? {
if i >= arr.count || arr[i].dash != depth { return nil } // Early exit
let node = TreeNode(arr[i].num)
i += 1
node.left = buildTree(depth + 1)
node.right = buildTree(depth + 1)
return node
}

@inline(__always)
func processInput(_ traversal: String) {
/ 2) // Preallocate to reduce reallocations
var dash = 0, num = 0, isReadingDashes = true

for ch in traversal.utf8 {
switch ch {
case 45: // '-'
dash += isReadingDashes ? 1 : 0
if !isReadingDashes {
arr.append((num, dash))
num = 0
dash = 1
isReadingDashes = true
}
default: // '0' to '9'
num = num * 10 + Int(ch) - 48
isReadingDashes = false
}
}
if !isReadingDashes { arr.append((num, dash)) }
}
}