Same Tree - Leetcode 100 - Python

0:00 - Read the problem
1:15 - Drawing Explanation
4:27 - Coding Explanation

leetcode 100

#same #tree #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[dmitributorchin]

The only thing that you should mention always when discussing a recursive solution is a possibility of a stack overflow. In this exact problem this is not an issue because it's mentioned there could be maximum 100 elements in a tree.
But if you fail to ask for a maximum possible number of elements in a data structure and you implement a recursive solution in an interview, you can expect to lose some points.

[nero]

A question like this makes me feel like a tree master lol, I'd pray to get asked this one on an interview

[pauljones]

He gets so excited it's contagious

[DrOvenProofStorm]

top notch youtube channel for real dude. Your explanations and organization of these videos are 👌.Keep up the good work!

[romelpascua]

Your videos have been helping me so much. We both use Python and your explanations are very clear so thank you!

[YashPratap]

Wow man. That was so much easier to understand than any of the discussions on the problem itself

[TenzDelek]

have never touch upon tree topic so when i first saw the question input, my mind immediately went on the solution of array which somehow works. just a one liner. return str(q)==str(p).

[rainneskye]

The code is simpler than I expected lol. Great work!

[MrMichalXXL]

actually a super easy explanation that makes the problem almost trivial

[rafik]

I think i am stupid a little bit, i used an approach to get the list of nodes of the first tree and the second tree using DFS or BFS and compare them, and to maintain the structure of the tree i inserted null to differentiate between different trees and the solution is time efficient but yours is really great and simple and have an average run time much more faster since it checks the condition each time so it can detect the False early.Thank u

[floatingfortress]

Thanks, I found this video to be helpful in arriving at a recursive solution :)

[mahdiranjbar]

In the worst case, where the two trees are identical, the runtime complexity is O(n), where n is the number of nodes in the trees.

[vishalgadhvi]

one of the best explanation for this question over youtube. ✨

[raviteja]

isnt the time complexity is Order of min(p, q)?

[f-s_interpreter]

class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
return str(p) == str(q)

[zeyadali]

I guess the complexity here will be O(min(p, q)), as you will return false once you find that they are not identical, yes we are traversing at the same time, but we don't use more time traversing the other tree.

[tomerva]

O(min(p, q)) since u return false early

[SOMESHKHANDELIA]

Created a string representation of both trees p and q using current level information of a node and whether current node is in left or right subtree of parent. Then compared the two strings:

class Solution {
public:
void get_string_rep(TreeNode* root, int curr_level, string &tree_str){
if(root == nullptr){
return;
}
else{
tree_str += to_string(root->val);
tree_str += to_string(curr_level);
if(root->left != nullptr){
tree_str += "L";
get_string_rep(root->left, curr_level+1, tree_str);
}
if(root->right != nullptr){
tree_str += "R";
get_string_rep(root->right, curr_level+1, tree_str);
}
}
}
bool isSameTree(TreeNode* p, TreeNode* q) {
string tree_str_p = "";
get_string_rep(p, 0, tree_str_p);
string tree_str_q = "";
get_string_rep(q, 0, tree_str_q);

// cout << "P: " << tree_str_p << endl;
// cout << "Q: " << tree_str_q << endl;

return tree_str_p == tree_str_q;
}
};

[GroveCleve]

when i tried to set this up in a code editor I got an error on the "if not p or not q or p.val != q.val" line saying p and q are ints (likely on the second time through).

I guess my question is how does the return line self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) work with the .left and .right values for p and q being ints?

I was able to get it to work if I altered
"if not p and not q"
to
"if (not p and not q) or p == q"

but that doesn't seem necessary for leetcode to pass it (though it does still pass).

thank you for the help and these videos have been so helpful.

[prajjwaldubey]

class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:

tree1=self.preOrder(p, [])
tree2=self.preOrder(q, [])
if(tree1==tree2):
return True
else:
return False
def preOrder(self, node, ans):
if(not node):
ans.append(None)
return
ans.append(node.val)
self.preOrder(node.left, ans)
self.preOrder(node.right, ans)
return ans

I have done this