My software development journey
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…
Given a set of numbers and a target value, we have to find if there is any subset whose sum is equal to the target value. For example let the array be {10, 34, 19, 27, 58, 45} and the target sum is 56, we have a subset {10,19,27} with the given sum. We don’t…
In this post I introduce you to a competitive programming problem called Jolly jumpers. This problem is available on UVa online judge on this link. UVa site is one of the first online judge websites which listed programming problems from different competitions like ACM ICPC and IOI and allowed users to solve and submit their…
Given an array of positive and negative numbers, how do we write a program to check if it has three elements with sum 0. For example, the array {-31, 19, -6, -45, 12, -8, 3, -77, 56, 29} contains {-31,12,19} with sum zero. One obvious solution is to examine each possible triplet of the array…
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 row wise and column wise sorted two dimensional array or matrix. How to search for an element efficiently? Example of the array can be int[][] matrix = { {1,3,5,7,9}, {10,12,14,16,18}, {19,21,23,25,27}, {28,30,32,34,36}, {37,39,41,43,45} }; This can be done using the following algorithm. We start our search with the top right element. If it…
Given array of elements we have to write a program to print the biggest element to it’s right for each of the elements in the given array. For example let us consider the array {3, 9, 2, 4, 6, 1}. The output for this array should be {9, 6, 6, 6, 1, -1}. As a…