Please reduce the quality of videos 🙃 your content is pretty awesome💖😋 but in the end when you show the code, it consumes lot of data(1080P) to see the code clearly 🥺
Great Explanation 👏 I had a doubt though, at 3:34, you said Inorder traversal as Root -> Left -> Right, which to my knowledge is Preorder traversal I suppose, and Inorder traversal is actually Left-> Root -> Right. I can understand that it must have occurred by mistake, it's quite obvious that the unrivaled king of DSA can't commit this kind of mistake, it must have gone unnoticed. I request you to correct it, otherwise, it may cause confusion to beginners.
That's mistake but after that he cover we can use similar traversal on right subtree ... we can use any traversal but same on both subtree whether its inorder, preorder or postorder,
Self Notes: 💡 Mirror property is left == right and right == left 💡 pre-order traversal on root->left subtree, (root, left, right) 💡 modified pre-order traversal on root->right subtree, (root, right, left) 💡 compare the node val's if they are the same 💡 Do both traversals at the same time 💡 if left is null or right is null, then both sides must match and return true (base case)
I don't understand one thing in worst case why space complexity is O(n) even in normal case also we will traverse all the nodes so ot will be O(n) there is no difference right
@@hyperme1831 The recursive stack space is O(Height) because at max no. of recursion calls in the stack will be = height. so in case of full binary tree(the one you are referring to as normal case) ,say with 3 levels(and 2^i nodes in each level where i is the level no. starting from 0); the SC=O(3). But in worst case(i.e. skew tree) it height=n. Therefore SC=O(N) in that case.
I think in the skewed example, your code will return in the very first step of the recursion. So, here the space complexity cannot be O(n). I believe the worst case would be O(log n) for a full binary tree that is say symmetric till the we reach one of the leaf node. Please clarify this aspect.
I understood TC but for SC in case of skewed BT then algorithm will stop at top itself since there are not nulls on both sides then how it will be O(n)? Correct me if I am missing anything.
Of what I think..... In case of left skewed tree, lh=some node but rh=NULL; In this piece of code, as rh is NULL it will have no val data member as such. if(lh->val != rh->val) return false; (A node pointing to NULL does not have any data members i.e.-: left,right or val). This is the reason we, every single time gives a base case - if(lh==NULL), to specify an exceptional case in terms, that if the node becomes NULL. So the execution skips this part - if(lh->val != rh->val) return false; and helper(lh->left,rh->right) begins to execute which stores a recursion stack space of left tree as O(N). So, SC - O(N).
I also thought the same. The worst case would be when we have a complete binary tree and the symmetric property is satisfied completely. In that case the worst case should be O(log n). Could some one correct me or clarify this aspect.
it'll be O(N) SC because the recursion is a DFS based -> think about the case when the tree has N / 2 nodes to the left of root (like a linked list, going towards left -> left -> left) and N / 2 nodes to the right of root (like a linked list, going towards right -> right -> right) ... now our recursion condition is ((return dfs(leftSubtree -> left, rightSubtree -> right) && ...)) so in this case -> the recursion will go deep to the last node -> basically O(N / 2) space will be used which will be O(N) to calculate, then only after returning -> the 2nd condition after (&& ...) will be checked for every recursion call -> and the answer eventually becomes false ... but the point is -> it did takes O(N) space I didn't mention it earlier but -> Of course put the 1 wrong placed node at the bottom of either the left subtree or the right subtree -> then it will return false from the bottom
can you explain why in function isSymmetricHelp in first condition we have used || and return left==right...can we use && instead and return true; i have tried using && and the code gives runntime error..i want to know why is it wrong?
bhaiya pdhate padhate bhul jaate hain ki inorder bolna hai ya preorder at 3:28 bhaiya likh preorder rhe hai or bol inorder rhe hain...no matter hume smjh aagya kaafi hai.. thank you bhaiya maza aagya
@@takeUforward bhai you are living legend recently i got package for 7lpa but i will really grind up in my last 6 months and then update you with good news.
00:01 Check if a binary tree is symmetric 00:50 Discussing about symmetrical binary trees in C++ and Java 02:00 Checking for symmetrical binary trees in C++ and Java 03:20 Understanding symmetrical binary trees 04:37 Check for Symmetrical Binary Trees 05:40 Symmetry is important in creating effective and efficient programs. 06:47 Check for Symmetry in Binary Trees 08:18 The video discusses checking for symmetrical binary trees in C++ and Java.
can you explain why in function isSymmetricHelp in first condition we have used || and return left==right...can we use && instead and return true; i have tried using && and the code gives runntime error..i want to know why is it wrong?
@@ManyaNayak-md7xr if you use && you cover only 1 case that is both are null but there are two more cases one is null second not..second is null first not ...so by taking || we cover all the three cases at once
Ohh.....A astrange thing happen with me first I tried these problem and successfully solved it with O(N) time and O(1) space. and then what the same code was written by Striver Bhaiyya too......
we can still optimize a little bit, instead of sending root both the times as arguments, we should send root-->left, root->right. because the first approach checks both sides of the root.(left and right).we dont need that.if we check for one side its enough. bool isSym(TreeNode*root1, TreeNode*root2) { if(root1 == NULL && root2 == NULL)return true; if(root1 == NULL || root2 == NULL)return false; if(root1->val != root2->val)return false; if(isSym(root1->left, root2->right) == false) return false; if(isSym(root1->right, root2->left) == false) return false; return true; } bool isSymmetric(TreeNode* root) { TreeNode*root1 = root->left; TreeNode*root2 = root->right; if(root1 == NULL && root2 == NULL)return true; if(root1 == NULL || root2 == NULL)return false; return isSym(root1, root2); }
Self Notes: 💡 Mirror property is left == right and right == left 💡 pre-order traversal on root->left subtree, (root, left, right) 💡 modified pre-order traversal on root->right subtree, (root, right, left) 💡 compare the node val's if they are the same 💡 Do both traversals at the same time 💡 if left is null or right is null, then both sides must match and return true (base case)
could you pls help me out to find below tree symmetric or not.? root = new Node(1); root->left = new Node(2); root->left->left = new Node(4); root->left->right = new Node(5); root->right = new Node(2); root->right->left = new Node(5); root->right->right = new Node(41);
PYTHON CODE : I think this is most optimised than the above one. No offense. It's the same concept he taught us in one of the video def solve(roota, rootb): if (roota==None) or (rootb==None): return roota==rootb if roota.data!=rootb.data: return False l = solve(roota.left, rootb.right) if l==False: return False r = solve(roota.right, rootb.left) if r==False: return False if l==False and r==False: return l return True def isSymmetrical(root): return (root==None) or solve(root.left, root.right)
this code will not pass all test cases it will not pass the test case if (right !=null &&left==null) || (right==null&&left !=null) return false; please add this base case
3 Approaches to solve this (1 DFS and 2 BFS) # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root: # If the tree is empty, it's symmetric return True ac # Use a helper function to perform DFS and check symmetry return self.dfs(root.left, root.right) def dfs(self, root1, root2): if not root1 or not root2: # If either node is null, check if both are null return root1 == root2 if root1.val != root2.val: # If the values of nodes are different, it's not symmetric return False # Recursively check the symmetry of the left and right subtrees return self.dfs(root1.left, root2.right) and self.dfs(root1.right, root2.left) class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root: # If the tree is empty, it's symmetric return True if not root.left or not root.right: # If either subtree is null, check if both are null return root.left == root.right # Use two queues to perform BFS and check symmetry queue1 = deque([root.left]) queue2 = deque([root.right]) while queue1 and queue2: # While both queues are not empty node1 = queue1.popleft() # Get the front node of the first queue node2 = queue2.popleft() # Get the front node of the second queue if node1.val != node2.val: # If the values of nodes are different, it's not symmetric return False # Check the right child of the first node with the left child of the second node if node1.right and node2.left: queue1.append(node1.right) queue2.append(node2.left) elif node1.right or node2.left: # If only one of them is null, it's not symmetric return False # Check the left child of the first node with the right child of the second node if node1.left and node2.right: queue1.append(node1.left) queue2.append(node2.right) elif node1.left or node2.right: # If only one of them is null, it's not symmetric return False return True class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root: # If the tree is empty, it's symmetric return True if not root.left or not root.right: # If either subtree is null, check if both are null return root.left == root.right # Use a queue to perform BFS and check symmetry queue = deque([(root.left, root.right)]) while queue: # While the queue is not empty root1, root2 = queue.popleft() # Get the front pair of nodes if not root1 and not root2: # If both nodes are null, continue to the next pair continue if not root1 or not root2: # If only one of them is null, it's not symmetric return False if root1.val != root2.val: # If the values of nodes are different, it's not symmetric return False # Append the children of the current pair of nodes to the queue for further checking queue.append((root1.left, root2.right)) queue.append((root1.right, root2.left)) return True
I have done using Palindrome, class Solution { public: bool isPalindrome(vector&v) { int N = v.size(); for(int i = 0; iright); v.push_back(x->val); } else v.push_back(101); q.pop(); } if(!isPalindrome(v)) return false; } return true; } };
I learned a lot from your graph series. This tree series is also amazing covering all important questions. Thank you! Keep posting such useful content.
💡 Mirror property is left == right and right == left 💡 pre-order traversal on root->left subtree, (root, left, right) 💡 modified pre-order traversal on root->right subtree, (root, right, left) 💡 compare the node val's if they are the same 💡 Do both traversals at the same time 💡 if left is null or right is null, then both sides must match and return true (base case)
One way to think about this is to consider the question where we are given two binary trees and asked to tell if they are the mirror of each other or not. So we check the root (if either of them is null) and then compare their value Once done. Now , we have to check for the left and right subtrees. like the left of the first subtree val should be equal to the right of the second subtree val and vice versa. now imagine all this in a single tree. Check if the root is null first(base case and also to avoid null pointer exception) and then apply the above logic to the left and right nodes of the same tree.(considering them as different) . Thank you, Striver! Your videos have really helped me improve my thought process and intuition.
create two trees from given tree. T1(root->left) T2(root->right) Find inOrder traversal of both tree (T1 and T2). The given tree will be symmetric tree if inOrder traversal of T1 is equal to the reverse of inOrder traversal of T2. void inOrder(Node * root, vector &l) { if(root==nullptr) return; inOrder(root->left,l); l.push_back(root->data); inOrder(root->right,l); } bool isSymmetric(struct Node* root) { // Code here if(root==nullptr) return true; vector left,right; inOrder(root->left,left); inOrder(root->right,right); reverse(right.begin(),right.end()); return left==right; } Thank you 😍😍
Great video! Another solution can be that the number of nodes must be odd and the inorder traversal of the tree is always a palindrome pseudo code- 1. store inorder traversal in a vector or suitable data structure 2. if(inorder.size()%2==0) return 0 return isPalindrome(inorder)
Hey, just sharing what I realised - I thought the same but it doesn't work always. 1 / \ 2 2 / / 2 2 The in-order traversal will give 2,2,1,2,2 and this a palindrome indeed but they are not symmetrical.
I have a doubt, are we performing in order traversal or pre order traversal? I think the answer can be achieved by either way but the technique we are using is probably pre order traversal. Please correct me if I am wrong.
Python code: class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root: return if not root.left or not root.right: return root.left==root.right def helper(lroot,rroot): if not lroot or not rroot: return lroot==rroot if lroot.val!=rroot.val: return False return helper(lroot.left,rroot.right)and helper(lroot.right,rroot.left) return helper(root.left,root.right)
@@tejas7379 It works: Check my code: class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: queue = deque() queue.append(root) while queue!=None: cur = [] size = len(queue) while size: size-=1 node = queue.popleft() if node==None: cur.append(None) continue cur.append(node.val) if node.left: queue.append(node.left) else: queue.append(None) if node.right: queue.append(node.right) else: queue.append(None) print(cur) if not self.isPal(cur): return False for i in cur: if i!=None: break else: return True def isPal(self,l): return l==l[::-1]
