Skip to main content

Posts

Showing posts from 2018

Bottom View of a Binary Tree

In this post, we will discuss a method to print the Bottom view of a binary tree. This is one the most common easy level interview questions. Also, you might get to see interview questions which can be solved with slight variations to this code. We will use a method that is very similar to printing Top View of a Binary Tree as discussed in our last post.

Bottom View of a tree is defined as the nodes that would be visible to us if we viewed the tree from the bottom. To do this we have to maintain a horizontal distance of all the nodes from the root node and print the last node for each horizontal distance. This problem can be solved easily with simple traversal and use of data structures. Have a look at the below image to get some idea.



In the above image, the horizontal distance of the root is set to 0 and for all the node to the right we increase the horizontal distance by 1 and for all the node to the right, we decrease the horizontal distance by 1. Thus, the problem reduces to printi…

Right view of a Binary Tree

In this post, we will discuss a method to print the Right view of a binary tree. This is one the most common easy level interview questions. Also, you might get to see interview questions which can be solved with slight variations to this code. The approach we take here is almost very similar to printing the Left view of the Binary Tree

The right view contains all nodes that are last nodes in their levels. Right View of a tree is defined as the nodes that would be visible to us from the right side. To do this we have to simply print the first node encountered while traversing a level from the right. If you have seen my post for the left view of the binary tree then the only change that we make here is to traverse the right child of the current node first and then traverse the left node. Have a look at the below image to get some idea.


There are 2 solutions to this problem, first is to do a recursive preorder traversal in which we maintain max level we have traversed and then print the n…

Left view of a Binary Tree

In this post, we will discuss a method to print the left view of a binary tree. This is one the most common easy level interview questions. Also, you might get to see interview questions which can be solved with slight variations to this code.
First, let's see what do we mean by the left view of a binary tree.The left view contains all nodes that are first nodes in their levels. Left View of a tree is defined as the nodes that would be visible to us from the left side. To do this we have to simply print the first node encountered while traversing a level from the left. Have a look at the below image to get some idea.




There are 2 solutions to this problem, first is to do a recursive preorder traversal in which we maintain max level we have traversed and then print the node if the max level is less than the max_level variable and update the max_level variable, another simple solution is to do level order traversal and print the first node in every level.

Method 1: Using Recursive Preor…

Check if a Linked List is Palindrome

In this post, We will discuss a method to check if a given string or number represented in the form Linked List is a Palindrome. First, let's see the definition of a Palindrome, A word, phrase or a sequence that reads the same backwards as forwards is called a Palindrome. eg. "MADAM", 11100111, "NURSES RUN".

Questions on palindrome, anagrams are very common in coding interviews and also very easy to solve if you have solved them before. There are a lot of methods to check If a string or a number is a palindrome or not. In this post, we will use the second method i.e pointers

First Approach: Using Stack

In this method we iterate over the string and for each character we compare the current character is same as that of character at the stack top if yes then we pop the element from the stack top else we push the current character onto the stack, after iterating over the string if the stack is empty then we can declare that the given string is a palindrome else the g…

Reversing first k nodes of a Linked List

In this post, we will discuss a method to reverse k nodes from the starting of the linked list. In one of my earlier post, we have already discussed methods to reverse a given linked list. Here We will create a method that accepts the head of the linked list and Number k that indicates the number of elements to be reversed. To do this we will be using a simple method to reverse the linked list with an additional condition in the while loop where decrease k after each iteration. Have a look at my previous post on Linked List in c++ to see how to reverse a linked list.

Let’s directly look at the algorithm and code to understand it better

Algorithm:
In the above code, we use 3 pointers current, previous and next. Initially, the current node points to the head node, the previous and next nodes are Null Then we use a while loop to traverse through the linked list and also decrease k In each iteration, we do the following assign next pointer to current node's link field update current nod…

Rotate Linked List

In this post, we will discuss a method to Rotate the Linked List in an Anti-clockwise direction. This is one of the easy questions asked in coding interviews. There are a lot of approaches that one can try using for this problem, below algorithm according to me is one of the simpler approaches if not the best. To rotate a linked list we simply need to link the tail node to the head node and move the head pointer to the next node, we repeat this step according to shift value. Let's have a look at below algorithm. We use 2 pointers for this algorithm, current node and tail node, the current node initially points to the head node and will become the new head node after our operations and tail node marks the end of the linked list.


Algorithm:


consider 2 nodes current node and tail node.Initialize current node to point to the head of the Linked ListInitialize tail node to point to the head of the Linked List Move the tail pointer and make tail point the last element Repeat the below step…

Adding one to number represented as Linked List

In this post, we will discuss a method to add one to a number which is represented using nodes of the linked list. 
This problem becomes very simple if the given linked list is considered to be doubly linked list as it is easier to add one to the number at the end of the linked list and traverse the list from backward direction till carry becomes zero. but if the given linked list is a singly linked list then we have to first reverse the given linked list and then add one to the first node. So considering our linked list is a simple linked list we follow the below steps.

Algorithm:
Reverse the linked list.Add one to the data field of the first node. While carry is not zero keep adding carry to the next node's data field if you reach the end of the linked list and the carry is not zero then we add a new node to the end of the linked list. Reverse the final linked list and return the head node of the linked list.

C++ ProgramJava programPython Program C++ Program Java Program Python Pr…

Delete kth element from end of Linked List

In this post, we will discuss a method to delete the kth element from the end of the linked list. In order to delete the required node, we first need to find the kth element from the end of the linked list and then we can delete that element, so in one of the previous posts we have discussed a method to find kth element from the end of the linked listand In another post we have seen a method to delete node from linked list with the only pointer to that node, So combining the 2 methods we can delete the kth element from the end of the linked list.

Have a look at the below posts for an explanation of the methods used in this post
Finding kth element from the end of the Linked list Deleting element from the Linked List with only pointer to that nodeAlgorithm
Initialize 2 pointers first and second to head node Move node first to the kth node from the start Move both first and second node through the list till the first node reaches the last node At this point, the second node points to th…

Deleting node with single pointer Linked List

In this post, we will discuss a simple method to delete a node when we have only the pointer of the node to be deleted and no link to the head or tail node. Deleting node with the only pointer to that node is one of the famous and very easy interview questions and is asked a lot. The method we use can be used for both simple or doubly linked list. To delete the given node, we can use the following method
Algorithm: Let the node to be deleted be called as the current node.Create a temp node to point to the next node.Now copy the contents of the temp node to the current node.copy the link field of the temp node to the link field of the current node.delete or free the memory pointer by the temp node.


C++ ProgramJava programPython Program C++ Program Java Program Python Program Sample input and output to check the program
You might also be interested in 
Singly Linked List
Double Linked List
Linked List in Python
Finding Kth element from the End of Linked List
Stack Implementation using Linked List

Finding kth element from end of Linked List

In one of my previous post I discussed a method to find the middle element of the linked list in single traversal using 2 pointers. In this post We will see a similar approach to find the kth element from the end of the linked list.
Finding the kth element from the end of the linked list is one of the famous interview questions and is asked a lot.
In order to find the kth element from the end of the linked list we use 2 pointers. Let the 2 pointers be first and second. now we initialize them to point at the head node of the linked list and move the second pointer to the kth node. After that we start traversing the linked list using both the pointer and keep moving them forward until the first pointer reaches the end of the linked list. as the difference between the position of the pointers is k places when the first node points the last node then the second pointer will point to the kth element from the end. So we can simply return the second pointer or the contents of the the node poin…