Easy Google Interview Question! | Symmetric Binary Tree - Leetcode 101

dynamic programming, leetcode, coding interview question, data structures, data structures and algorithms, faang

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[rahuldwivedi]

Easy but not ‘very easy’ for sure. It’s not totally intuitive to come up with sym(root, root)

[jonm]

do a DFS on the right side favoring the right first. Do a DFS check on the left side favoring the left first, if any don’t match return false. Also works with BFS. O(n), half is traversed and other half is checked so between 1/2 to 1 of the n

[ink]

easier to make an inorder traversal of the tree (2, 3, 1, 3, 2) and check if its equal to its reverse. Zero thinking required

[gnes]

If you've done a few tree problems and know recursion this is very easy

[mariogalindoq]

Are you doing the full comparison two times? That is, when root1==root2==root, you execute sym(root1.left, root2.right) that verify all the tree but, you are also doing sym(root1.right, root2.left) that repeats all the comparison a second time. I think you should include before the las line of the function: if root1==root2: return sym(root1.left, root2.right) isn´t it?

[JustinLietz]

Understanding data structures and algorithms conceptually can be straightforward, yet unfamiliar syntax may lead to overly complex implementations.

I think this is the reason why people find some “easy” problems complicated and difficult, at least that’s the case for me.

[cristeycrouler]

Good video man love the problem choices

[zaringers]

But what matters is not the solution, rather how you come up with the solution on your own…

[rahuldwivedi]

While this recursive looks smoother to eyes. It might be difficult to come up with the approach if not solved before. Also, it’s slow and consumes a lot of extra space that’s not needed. How about this?

var isSymmetric = function(root) {
var q = [root];

while(q.length){
var l=0, r=q.length-1;

while(l<r){
if(q[l] === null && q[r] === null){
l++; r--; continue;
}
if(q[l] === null && q[r]!== null) return false;
if(q[r] === null && q[l]!== null) return false;

if(q[l].val !== q[r].val) return false;

l++;
r--
}
var n = q.length;

while(n!==0){
const front = q.shift();
if(front!==null){
q.push(front.left);
q.push(front.right);
}
n--;
}

}
return true;
};

[VAIBHAVMALHOTRA]

Easy to understand and even make a diagram but very difficult to type the code

[bkxogjk]

for some reason i just dont get recursion... i mean i get the general concept, but it feels like there's a mental block for me that stops me from actually creating any recursive solutions... if someone else ever got over that do lemme know how, it'd help a lot... i think its a pretty cool thing and i hate not being able to do it

[nerdycatgamer]

people saying this is unintuitive really need to study more or just see recursion more often. this is the most basic solution logically and can probably be reduced to like 5 lines (depending on your language perhaps).

this probably isn't even the best solution. my expectation was that this would be the obvious solution that the interviewer is expecting but probably wouldn't get many points for. i feel like there is probably a more efficient algorithm that is iterative rather than recursive

[vitorgobatogercov]

You will never need this level of logic on a daily basis

[Minalinsky]

It was an interesting exercise on one of the courses taught in college, It was fun to do it in C. Now I forgot how to do it quickly.

[utkarshsingh]

How about bfs solution.. push child nodes in queue as well as insert in array, left & right pointer to compare elements in array.

[ajitsdeshpande]

@GregHogg - While constructing the tuple why did you use sorted( 4 numbers)?
Does the problem description say such ordering constraint?

[Merlin_G]

Well, there is a mistake, a tree formed with only one branch on each side is a mirror of itself, but in your algorithm it would return false

[MaverickJeyKidding]

that was the first solution that came up to my mind. How can you solve this differently? It's a natural comparing process from the real life, is it not?

[jsalsman]

I would consider hiring someone who did this without using recursion. Recursion has no place in production code.