Constructing a balanced Binary Search Tree from a sorted List in O(N) time

This post discusses a O(n) algorithm that construct a balanced binary search tree (BST) from a sorted list. For instance, consider that we are given a sorted list: [1,2,3,4,5,6,7]. We have to construct a balanced BST as follows.

        4
        |
    2        6 
    |        |
  1   3   5     7

To do so, we use the following definition of Tree, described in Scala By Example book.

abstract class IntSet
case object Empty extends IntSet
case class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet

One straight-forward approach would be to repeatedly perform binary search on the given list to find the median of the list, and then, to construct a balanced BST recursively. Complexity of such approach is O(nlogn), where n is the number of elements in the given list.

A better algorithm constructs balanced BST while iterating the list only once. It begins with the leaf nodes and construct the tree in a bottom-up manner. As such, it avoids repeated binary searches and achieves better runtime complexity (i.e., O(n), where n is the total number of elements in the given list). Following Scala code outlines this algorithm, which effectively converts a list ls to an IntSet, a balanced BST:

Any comment or query regarding this post is highly appreciated. Thanks.

Passing Parameter to a Predicate in .Net2.0

In this post, we will see how to pass parameter to a method representing Predicate. 

Let’s say, we have a collection of SprintBacklogItems and we want to filter all the SprintBacklogItem with Title start’s with, let say “QA” or “Dev Task” depending on a input parameter. Now from the previous post https://adilakhter.wordpress.com/2008/01/11/using-predicate-actor-of-net20/  we know that , predicate only have 1 parameter of type T.

image

Then, how to pass a input parameter _HeaderToSearch in Predicate?

1. To do that, we need to a new object called ListMatcher –

public class ListMatcher 
   { 
       private string _HeaderToSearch; 
       public ListMatcher(string headerToSearch) 
       { 
           _HeaderToSearch = headerToSearch; 
       }  

       public bool Predicate(SprintBacklogItem item) 
       { 
           return item.Title.StartsWith(_HeaderToSearch, StringComparison.InvariantCultureIgnoreCase); 
       }  

   }  

2. Next , I initialized the ListMatcher object and use the HeaderToSearch  to filter the items- 

ListMatcher matcher = new ListMatcher("QA"); 
this.FindAll(matcher.Predicate);

Done.:)

Using Predicate & Action of .Net2.0

While I started developing software, I faced this situation over and over again where I had to iterate thorough the whole collection and perform some action on each of the element of the collection or filter elements depending on some logic. It was really annoying to  write same for/foreach loop again and again.

.Net framework2.0 resolve this issue where we can just tell the collection how to filter / how to perform some action on each element of the collection and it take care of the iteration part.  Let’s check out the List<T> Class of System.Collections.Generic and what support it provides –

image 

Huge support for Searching, Sorting and Filtering!!! If we look at the declaration of let’s say – FindAll and ForEach  –

public List<T> FindAll(Predicate<T> match);public void ForEach(Action<T> action);

Here Predicate and Actor are the generic delegate which gives us the flexibility to provide a way to filter the collection or perform action to each and every element of the List. Let’s dig deeper inside them –

Inside Predicate:

Predicate is a Generic Delegate which takes support from the new generic feature of .Net Framework2.0. It is defined –

delegate bool Predicate<T>(T obj)

As per definition of MSDN, Predicate

“represents a method that defines a set of criteria and determines whether the specific object meets this criteria.”

In short, Predicate is just a generic delegate that takes T as object and check whether the object fulfill some criteria and depending on that return true|false.

Example

In this example, by using Predicate, we are going to tell the Collection how to filter and Collection will handle the whole iteration and filtering process –

Let’s say, we have a collection of SprintBacklogItem and we want to filter them depending on there State == Closed, we can do it using predicate –

1. Define a method that represents the Predicate –

private bool HasStateClosed(SprintBacklogItem item) 
        { 
            if (item.State == SprintBackLogStatesStrings.CLOSED) 
                return true; 
            return false; 
        }

This method simply checks whether the SprintBacklogItem’s state is closed or not and depending on that , return true or false. Now, if we look at the declaration of the method , we are affirmative that we can use Predicate to represent this method.

2.  Following line of code filters all the closed SprintBacklogItems –

List<SprintBacklogItem> closedItems= _SprintBackLogsItems.FindAll(HasStateClosed);

Inside Action:

Similar to Predicate,

“Action is also one kind of generic delegate which represents a method that take the object as input and perform some operation on that.”

Definition of Action delegate-

delegate void Action<T>(T obj);

From the signature of the delegate, it can represent the method with signature that must have one parameter passed to it and void as return type.

In List<T> , the method represented by the Action delegate takes an input obj and perform actions on that.

Example

In this example, by using Action, we are going to perform some predefined actions( initializing ActualHour = 10) on each elements of the List –

1. Define the method that will be represented by Action –

public void InitActualHour(SprintBacklogItem item) 
        { 
            item.ActualHour = 10; 
        }

2. Following line of code initialize all the elements’ Actual hour to 10 of the List –

this.ForEach(InitActualHour);

Isn’t it pretty cool and slick ? Instead of implementing methods for Actor and Predicate , we could have used Anonymous Delegate. I will cover that topic in my future posts. Bye for now. :)