Category Archives: Data structures

Longest path in a binary tree

Given a binary tree, how do we find the longest distance between any two nodes in it? Some times this is referred to as the diameter of the tree.
For example consider the below binary tree

The longest path in this tree is 1 – 2 – 3 – 5 – 8 – 6 – 7. In this example the longest path passes through the root node. Sometimes it may not pass through the root. Checkout the next example.

The longest path 27-28-24-36-42-59-55 does not include the root node.

Here is how we can find the longest path recursively. We know that the height of the binary tree is the longest path from the root node to any leaf node.(Read this post to know more). Diameter is the maximum of the following.

Height(left subtree) + Height(right subtree) + 1
Diameter(left subtree)
Diameter(right subtree)

Here is the C++ implementation of the above. This program calculates the number of nodes on the longest path. The time complexity for this solution is O(n2). For optimal implementation, you can checkout this post.

Finding the longest consecutive subset

Given an array of positive and negative numbers(distinct), How do we find the length of the longest consecutive subset?

For example consider the below array
{3, 6, 1, 2, 5, 7, 8}
It contains {5,6,7,8} as the longest consecutive subset. So the answer is 4.
Similarly for {2, 4, 6, 8}, the answer is 1 as there are no consecutive numbers.

Lets discuss two algorithms to solve this problem.

Method based on sorting: 
We sort all the elements in ascending order. This would take O(n log n) time. Then we compare the adjacent elements to check if they are consecutive. If any two elements are not consecutive, we break the sequence and update the maximum length. getMaxConsecutiveSubset1() method in the code implements this algorithm. The overall complexity of this algorithm is
O(n log n).
 
Method based on Hash map:

Let us take a Hash map which stores the all the elements with a flag for each which indicates if it is visited or not visited.
  • Initially we store all the elements to the map with visited flag as false. 
  • For each element do the following 
    • If it is not visited earlier 
      • Mark the element as visited 
      • Initiate a sequence of length 1 
      • Try to extend this sequence backward by marking the elements visited 
      • Try to extend this sequence forward by marking the elements visited 
      • Update the maximum sequence length

Here is the Java code which implements the above algorithm. It runs in O(n) time and O(n) space.

Number of characters appearing in all given strings

Given a set of n strings, we have to write a program to find out the number of characters appearing in all the strings.

For example consider the following strings
{“India”, “China”, “United states”}, the letters {a,i,n} appear in all the strings.

Let us think of the following solution.
  • We first add all the characters in the first string to a set. 
  • For each string we do the following.
    • For each letter in the set, we check if it can be found the string.
    • If it is not found, we delete it from the set
  • Finally the set contains only the elements which appear in all the given strings.

Here is the C++ code which implements the above approach. For simplicity this program assumes that all the strings contains lower case alphabets only.

Reversing a linked list in groups of given size

Given a single linked list, and an integer k, we need to reverse the linked list in groups of size k.
For example consider the following diagram of input and output linked lists for k = 3.

There are no tricks involved in the solution for this problem. It is just an implementation challenge where we have to carefully manipulate pointers to achieve the desired result.

Here is the strategy. The first step is to subdivide the list into chunks of size k. The last chunk maybe less than size k (depends on whether the length of the linked list is a multiple of k).

Keep a reference to the beginning of the sub-list, and traverse through k nodes.
Reverse the sub-list and re-arrange the begin and end pointers for the reversed sub-list.
The following diagram might give an overview of the process.
Here is the C++ implementation including recursive as well as iterative implementation.
We can consider the following test cases to test the program.
  • An empty/NULL list
  • List with just one node
  • List with multiple of k size
  • List with non-multiple of k size
  • Arbitrary list with k = 0, k= 1, k= length(list)
  • Any combination of the above.

Building a binary tree using inorder and post/pre order traversals

Given the in-order, and pre-order or post-order sequences of a binary tree, how do we construct a binary tree from them?

Given only pre-order and post order traversals, we can not construct a unique binary tree from them.

For example given 
In-order : {1, 2, 3, 4, 5, 6, 7, 8}
Pre-order: {5, 3, 2, 1, 4, 8, 6, 7}

We have to create the following binary tree

We use recursive approach for constructing a binary tree from In-order and Post-order or Pre-order traversals .

Constructing from Inorder and Preorder:

In Pre order, we first traverse the root, then left sub tree and right sub tree. So the first element in the pre order is always the root. We search for this element in the in-order sequence. This index divides the in-order sequence into left subtree and right subtree.

For example consider the following binary tree
                
                       1
               /  
              2     3
             /    /    
            4   5 6   7

Inorder:  {4, 2, 5, 1, 6, 3, 7}
Preorder: {1, 2, 4, 5, 3, 6, 7}

Create 1 as the root node, 

  • all the left elements to the left of it {4, 2, 5} form the left subtree
  • all the elements to the right of it {6, 3, 7} form the right subtree


We can use the index of 1 in Inorder (in this case 3) to calculate the size of the left and right subtrees.

Size(left subtree) = index
Size(right subtree) = size-index-1

We can also use this index to calculate the offset of Inorder and Post order sequences for the subtree.

To create the left subtree we pass Inorder:{4, 2, 5} Preorder:{2, 4, 5} as parameters to the recursive call.

To create the right subtree we pass Inorder:{6, 3, 7} Preorder:{3, 6, 7} as parameters.

Constructing from Inorder and Postorder:

In post order, we first traverse the left subtree, right subtree and visit the root. So the last element in the post order sequence is the root.
Similar to the above algorithm, this element divides the in-order sequence into left subtree and right subtree.

Considering the same example as above the Post order is {4, 5, 2, 6, 7, 3, 1}
Once we create the root with the last element i.e 1. 

We pass the following parameters to create the left and right subtrees.

                       Inorder                 Postorder
Left Subtree    {4, 2, 5}                {4, 5, 2}
Right Subtree   {6, 3, 7}                {6, 7, 3}

Here is the C++ implementation of the above two algorithms.

Finding the number of duplicates in a list of numbers

Given a list of numbers, we have to find how many duplicate entries are present in it?

For example consider the list of numbers {5, 1, 9, 5, 2, 1, 6, 4, 5, 8}
It has 3 duplicate numbers.

There are many ways to do this. In this post, I present one of the simplest ways using C++ STL set data structure, and Java HashSet data structure
 
The insert() method of the set returns a pair of type 
pair< set<type>::iterator, bool >
 

The second value in the pair is true if a new element is inserted. It is false if there is already an existing element.

The add() method of HashSet returns true if new element is inserted, and false if no new element is inserted(duplicate)

We can make use of this property to count the number of duplicate elements.

Here is the simple C++ implementation.

Here is the Java Implementation.

Counting the number of leaf nodes in a binary tree

Given a binary tree, write a program to count the number of leaf nodes. A leaf node is a node which does not have left and right children.

For example consider the following binary tree.

It has 3 leaf nodes namely 1, 4 and 7.

The solution is simple. The number of leaf nodes of a binary tree rooted at R is the sum of leaf nodes in the left and sub trees. Using this property we can devise a simple recursive solution.

This can also be solved using iterative solution by traversing the binary tree using BFS (Breadth First Search) traversal.

The following C++ program shows both recursive and iterative implementations.

Deleting duplicate elements from a sorted linked list

Given a sorted linked list, how do we delete duplicate nodes from it?

This question is simple and straightforward, we take two pointers, current and next which points the adjacent nodes. In each iteration we compare the values at these two nodes, if they are equal, we delete the node pointed by next and advance the two pointers. Take a look at the following diagram to get better understanding.

Here is the C++ implementation

Splitting the linked list into two halves

Given a single linked list, how do we split it into two halves.

For example the list 1->2->3->4 should be divided into 1->2 and 3->4
If the length of the list is odd, add the extra node to first half; so 1->2->3 should be split to 1->2 and 3.

This problem can be efficiently solved using fast pointer, slow pointer mechanism explained in this post.
In this approach, the fast pointer moves two steps at a time where as the slow pointer moves one step at a time. By the time the fast pointer reaches the end of the list, slow pointer will be pointing to the end node of the first half. So we need to iterate the list only once.

Here is the C++ implementation.

Sorting a linked list using insertion sort

In one of my previous posts, we have seen how a linked list can be sorted using bubble sort approach. In this post we will see how we can sort a linked list using insertion sort algorithm. Like bubble sort this approach will also take O(n2) time.

Here is the strategy for linked list insertion sort. We maintain two lists; one sorted and another unsorted. Initially the sorted list is empty and the unsorted list will be the original list. In each iteration, we remove a node from the unsorted list and add it the sorted list in proper position. I re-used the procedure for inserting data into a sorted linked list from this post.

The following diagram should give you some understanding of the procedure.

Here is the C++ implementation of the above algorithm.