Recover a Tree From Preorder Traversal - Leetcode 1028 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
15:26 - Coding Explanation

leetcode 1028

#neetcode #leetcode #python

[DNKF]

I think this question fit in the Hard category and Leetcode has to introduce a new category "Extreme Hard" for those really crazy problems like KMP or other special ones.

[baetz]

I'm not that good with stacks, so I've been putting every node I discover into map where key is level and value is a list of nodes. When I find the level and value of a current node, I add it as a left (or right if left is taken) child to the last node of the previous level. Essentially the same algorithm but with some extra space overhead. It's so useful to watch the video even after the problem is done! There is always something to learn. The mustache is good btw!

[AI_for_funn]

// java code

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode recoverFromPreorder(String traversal) {

int i=0;
int dashes = 0;
Stack<TreeNode> st = new Stack<>();
int n = traversal.length();
int j=0;

while(i<n)
{
char ch = traversal.charAt(i);

if(ch=='-'){
i++;
dashes++;
}
else
{
j=i;
while(j<n && traversal.charAt(j)!='-'){
j++;
}
int value = Integer.parseInt(traversal.substring(i, j));

TreeNode node = new TreeNode(value);

while(st.size()> dashes){
st.pop();
}


if(!st.isEmpty() && st.peek().left == null){
st.peek().left = node;
} else if(!st.isEmpty() && st.peek().right == null) {
st.peek().right = node;
}

st.push(node);
i=j;
dashes=0;
}
}
while (st.size() > 1) {
st.pop();
}
return st.peek();
}
}

[Kaviarasu_S]

"Today is kinda of one of those days for me I'm little bit tired but I mean who isn't" - Navdeep

[LeonLeonLeonardo]

Awesome solution and great intuition – and that mustache is on point!

[slashdt]

The mustache lookin mighty fine! Thank you so much for your solutions.

[yhbarve]

Good problem. Better solution. Best mustache!

[Biradar_Ganesh]

The mustache looks good.
I have used another approach, and the time and space complexity remain the same.
I was amazed that I solved it all by myself😁😁, it took me just 15 minutes to come up with the approach.

I would use a hashmap (unsorted map) with the key as the depth (0-based) and value as TreeNode.
- As I traverse through the given string, i will keep track of dashes and when i get a number, i will create a node
- i would access it's parent using the map (map[dashCnt - 1]), then attach the currNode to its parent
- to make sure i will add the childrens at correct positions (basically to correct parent), i will keep updating the keys(dashCnt i.e., depth) with the latest currNode.

here's my approach,

class Solution {
public:
TreeNode* recoverFromPreorder(string traversal) {
int n = traversal.length();
if(n == 0) return nullptr;
unordered_map<int, TreeNode*> mpp; // depth(zero based), node
int i = 0;
// first get the root node
string num = "";
while(i < n && traversal[i] != '-'){
num.push_back(traversal[i]);
i++;
}
TreeNode* root = new TreeNode(stoi(num)); // got the root node
mpp[0] = root;
// now start the traversal for remaining nodes
while(i < n){
int dashCnt = 0;
while(i < n && traversal[i] == '-'){
i++;
dashCnt++;
}
num = "";
while(i < n && traversal[i] != '-'){
num.push_back(traversal[i]);
i++;
}
TreeNode* curr = new TreeNode(stoi(num));

if(mpp[dashCnt-1]->left == nullptr){
mpp[dashCnt-1]->left = curr;
}else{
mpp[dashCnt-1]->right = curr;
}
mpp[dashCnt] = curr; // updating the depth (dashCnt) with the latest currNode

}
return root;
}
};

[SandeepWithAI]

That's really a tricky solution i loved it... Thanks NeetCode

[hetparekh]

I used to hate recursion but now I find the recursion solution more intuitive and easier than the stack one

[damodar___]

Always had fun using stack for DFS, today it has come for a save.
Going hard with 23 days of coding streak 🔥

[ChrisBakare]

1:30 hours but I got it done. Its a hard so I let myself go through it at my pace

[cooldoce]

Suggest trying to apply a monolithic stack.

[hrishii.]

Couldn't really solve on my own. The relation between Len(stack) and depth was beautiful, once I got that from the video was able to code it on my own!

[howardlam]

It wasn't even 22nd in the US yet. Does Leetcode update questions for the whole world at 00:00 london time for the whole world?

[matthewvaccaro]

Neet is trying to dethrone prime with the stach action!

[varunharalalka]

I just used recursion and backtracking to solve it

[Nishanth_S]

Hey 😮 Where is Navdeep?

Not gonna lie, you are cooler than him.

[PranavRPise]

Yeah this seemed like a medium at first glance but I guess it required some critical thinking for an optimal solution.

[vaseemshaik]

Why did this new mustache guy replace Navdeep!!!