My software development journey
Given a binary tree, we have to print the data level wise. For example level order traversal of the following tree produces the sequence 5,3,8,2,4,6,1,7. The hint to solve this problem is to use a Queue data structure. We start by inserting the root node into the queue. Until the queue is empty, we remove…
Given a binary search tree, how do we find the maximum and minimum elements in it? For example in the given tree, the maximum element is 8 and the minimum element is 1. This algorithm is based on the following simple observation. In a Binary search tree, the minimum element always lies on the left…
Traversal algorithms of non-linear data structures like trees are designed to visit/print all the elements in that structure. There are three main traversals of the binary tree. Namely In-order traversal Post-order traversal Pre-order traversal In addition to these, there are inverses of the above algorithms, and there is a level order traversal. In this post…
Given a binary tree how to find the height of the tree. It is defined as the number of nodes in the longest path from root to any leaf. We can assume that the height of empty tree is 0 and the height of a tree with just root node as 1. For example the…
A binary search tree is a hierarchical data structure which stores data in a non-linear fashion. It supports the insertion, search and deletion operations in O( log n ) time. Take a look at the below picture. This is an example of binary search tree. The node at the top containing 5 is the root…
Given a sorted linked list, We have to delete all the duplicates in that list. For example, If we get the following list 1 -> 1 -> 2 -> 3 -> 3 -> 3 -> 4 -> 4 -> 5 The output should be 1 -> 2 -> 3 -> 4 ->5 To solve this…
How do we sort a linked list? In this post, we see one such method using bubble sort algorithm. We have discussed the Bubble sort algorithm on arrays in my previous post. The same algorithm is also applicable to singly linked lists as well.We first find the length of the linked list (len). The outer loop…
Given a linked list, how do efficiently find the nth node from the end? For example in the following linked list, 3rd node from the end is ‘6’. 2 -> 1 -> 6 -> 5 -> 9 One obvious method is to find the length of the linked list (len) by going through the list.…
Given a sorted linked list, how do we insert data into the list in proper order? This is nothing but a step in insertion sort. Simply iterate through the elements to find the position for given number and insert at that position. Here is the Java code to do that. I have used the LinkedList…
Given a Binary Search Tree (BST), How do we find the Lowest Common Ancestor (LCA) of the given two nodes? For example in the following BST, the LCA of 5 and 8 is 7 because it is the nearest ancestor common to both the nodes. Let us assume that the LCA(5,7) is 7 itself (…