Skip to main content

Posts

How to Invert A Binary Tree (Iteratively + Recursively)?

Inverting a binary is one of the most common questions being asked these days. Often, seen many times in the ad of AlgoExpert as well. So, what is an inverted binary tree? Inverted binary tree is a simply a mirror image of given binary tree. Example : So, all we need to do is " Swapping left children with right children of a binary tree at every level." Implementation Recursively TreeNode* invertTree(TreeNode* root) { if(root==NULL) return NULL; swap(root->left,root->right); invertTree(root->left); invertTree(root->right); return root; } Iteratively TreeNode* invertTree(TreeNode* root) { if(root==NULL) return NULL; queue<TreeNode*> q; q.push(root); while(!q.empty()) { TreeNode* c= q.front(); q.pop(); swap(c->left,c->right); if(c->left!=NULL) q.push(c->left); if(c->right!=NULL) q.push(c->right); } return root; } I hope this tutorial hel...

Symmetric and Identical Trees

In this blog, we're going to cover Symmetric Tree and Identical Tree problems. These are quite similar problems, in the Symmetric tree we are provided with a single tree, but for checking identical trees we're provided two trees. What is a Symmetric Tree? A tree is called symmetric if it contains a mirror image of itself when divided from the center(root). This means that the left portion of the tree should be symmetric to the right portion of the tree. Example of a Symmetric Tree: What are Identical Trees? Two trees are said to be identical when they have the same data and the arrangement of data is also the same in them. Example of Identical Trees: In symmetric trees, the left portion of the tree is compared to the right portion of the tree. Whereas in the case of identical trees the left portion of one tree is compared with the left portion of another tree similarly, the right portion of one tree is compared with the right portion of another tree. Implementation Symmetric Tr...

Least Common Ancestor (LCA) of a BST & Binary Tree

The least Common Ancestor is one of those problems which appear quite complicated, but is pretty straightforward and can be solved easily.  So in this blog, we're going to understand how to find LCA in a BST & a Binary Tree. Given a binary tree and two nodes n1=1 & n2=4, so the first common node for n1 & n2 with the minimum difference in their heights is 3, therefore 3 is the LCA for n1 & n2. Let's discuss where cases to make you understand LCA better: For n1 = 2, n2 = 3  LCA=> 3 For n1 = 4, n2 = 8  LCA=> 5 For n1 = 7, n2 = 9  LCA=> 8 So now let's try to find LCA in a Binary Search Tree: In a binary search tree, the elements to the left of the root are smaller than the root, and elements to the right of the root are greater than the root. We can find the LCA according to the following conditions : Both n1 & n2 are smaller than the root so, LCA will be in the left sub-tree. Both n1 & n2 are greater than the root so, LCA will be in the ...

Zig-Zag & Spiral Traversal Of A Binary Tree Made Easy

Zig-Zag and Spiral Traversal of a Binary Tree are some of those problems which appear different but have a lot of things in common and thus, can also be solved easily using a common approach. Let's understand what a Zig-Zag & Spiral traversal exactly is : Zig-Zag traversal for the above binary tree is :                                                                                1                                                                            3      2             ...

Top & Bottom View Of a Binary Tree Made Easy!

In the previous blog, I wrote about finding Left & Right view of a Binary Tree . In this blog, I'm going to talk about Top & Bottom view of a binary tree and will again try to create a single approach that will solve both the problems so instead of understanding two different approaches we'll discuss a single approach for it. Firstly, let us understand " What is the Top/Bottom view of a binary tree? ". When a tree is viewed from the Top/Bottom then the only nodes visible from that particular view are printed/included in output. For example : For the above mentioned binary tree nodes in Top & Bottom View are as follows : Top View -> 4, 2, 1, 3, 6 Bottom View -> 4, 7, 5, 8, 6 Let's try to understand it for the top view and the bottom view will be similar with minor changes. Looking from the top 4 is visible so we've included it in our top view, similarly, 2 is visible so we've included it in our top view, 7 is getting overlapped by 2 so we...

Left & Right View Of a Binary Tree Made Easy!

When talking about binary trees then the view of a binary tree is something that has the most probability to be asked in a coding interview. In this blog post, I'm going to talk mainly about the Right & Left views of a binary tree. There are so many ways available on the internet, that it's really a very difficult task to choose which method you should follow. Suppose, you're using one method for Left View and another method for Right View, now you need to know two different methods for two similar questions. In this blog we'll discuss a single approach by which you can solve both Left View and Right View problems.   Before diving directly into the approach we need to understand what exactly is this Right/Left view. For your better understanding I've created a binary tree : So let's try to understand the right view for this binary tree. Right View simply means looking at the tree from its right side and the only nodes visible from that view are required to b...

Tree Traversals Made Easy!

In this blog, I'm going to discuss one of the easiest ways by which you can traverse a binary tree. Structure Of Tree struct node { int data; node *right,*left; node(int data) { this->data=data; left=right=NULL; } }; Tree   traversal   Pre-order :  Root -> Left -> Right   void preorder(node* root) { if(root==NULL) // base condition return ; cout< data<<" "; // print root preorder(root->left); // go to left child preorder(root->right); // go to right child } In-order : Left -> Root -> Right void inorder(node* root) {     if(root==NULL)         return ;     inorder(root->left);     cout<<root->data<<" ";     inorder(root->right); } Post-order : Left -> Right -> Root  void postorder(node* root) {     if(root==NULL)         return ;   ...

Things No One Will Tell You After Getting Into Computer Science Engineering

 Hey Folks! In this post, I'm going to talk about the things I wish someone told me when I got into engineering. These questions are received by me on a Daily Basis  Which is the best programming language to learn?  There is no bar for learning a programming language but I recommend you to learn Java/C++. The reason is that the level of abstraction in it is quite less and you get to know the logic behind the working of various functions and algorithms. You can refer to this post for a detailed explanation  : Best Programming Language Can I get a placement on the basis of my CGPA?   Will my CGPA matter?  Will my class 10th and 12th marks matter for placements?  CGPA is an indicator that tells how good are you in understanding the subjective knowledge of your degree. A good CGPA can be obtained by learning things and doing everything on time (theoretically) but (practically) all of us know engineers study 1 day before exams this will enable you to p...

On Which Coding Platform Should I Practice?

Which is the best online platform to practice, how to improve my coding skills? This post is all about giving answers to all such questions. If you're a beginner who has got no idea what programming is then I would recommend you step by step practice any programming language on Hackerrank. Hackerrank has modules that are self-explanatory and would slowly make you understand all the terminologies which are generally used and with practice, you'll be better at it. Moreover, if you're still not able to understand anything you can always search for your answers on GeekForGeeks or HackerEarth both of them provide one of the best tutorials on any topic. If you're an intermediate who's comfortable with any programming language then you can always improve your problem-solving skills studying Data Structures and Algorithms and practicing it. You can also improve by competitive coding. The best place to start with competitive programming according to me would be ...

100+ STL Algorithms, "I Bet If You Know Even 20 Out of These..." ( C++ 17 )

So, In the previous posts, I've been telling you about the various containers in STL and their implementation. I left a few of them purposely such as unordered_map, unordred_set, etc. so that you also do some homework. This post will entirely be about various functions available in STL and it would be your task to completely code & implement them. Do tell me if you have any doubts related to it in the comment section below. Some common Data Structures Implementation In STL : Stack Syntax : stack<data_type> stack_name Example  : stack<int> st; Built-in functions such as top() ,  push() , pop() , empty() , size() etc. are available in STL for Stack. Queue Syntax :  queue<data_type> queue_name Example  :  queue<int> q; Built-in functions such as push() , pop() , empty() , size() , front() , back() are available in STL for Queue. List ( Doubly Linked List ) Syntax :  list<data_type> list_name Exampl...