Entity Framework Core Migrations with Azure Service Fabric

Entity Framework Core migrations are really powerful and most C# developers make good use of them. They’re very easy to use, you can work with them either on Powershell or on the Package Manager Console. Most of the time whenever you make some change in your Entities you can open up a terminal and hit “dotnet ef migrations add” followed by a name for your new migration.

This will work on all ASP.NET Core projects by default. However, when creating a Service Fabric Stateless or Stateful microservice, things are different. If you attempt to run this command it won’t work. You will receive an error like the following:

Unable to create an object of type ‘AppDbContext’. Add an implementation of ‘IDesignTimeDbContextFactory‘ to the project, or see https://go.microsoft.com/fwlink/?linkid=851728 for additional patterns supported at design time.

The first step to debugging this error is to re-run the command in verbose mode:

dotnet ef migrations add "InitialMigration" --verbose

By taking a closer look to the console output we can see that the actual error that broke the operation is the following exception:

System.MissingMethodException: No parameterless constructor defined for this object.

Every time you run that command without supplying any other arguments, .NET Core will re-build your project, execute Program.cs to load the webhost and more specifically the Startup file. This is important because without the startup file, it will be impossible for the runtime to know how to instantiate the Database Context.

This is an example of an AppDbContext:

We only have one entity, the ToDo model and we inherit from Entity Framework’s DbContext. If you look at the constructor, you can see that in order to create a new instance of this class we have to pass an argument of type DbContextOptions. The most common option in that object is the connection string that will allow Entity Framework to locate our database. The options object is created by a DbContextOptionsBuilder in the startup class at the time of registration like this:

So what is really happening is that the runtime can’t provide DbContextOptions so it resorts to calling the parameter-less constructor. But there’s no such thing. We haven’t implemented one. And it’s neither the best choice nor possible sometimes. So, the framework suggests we implement the IDesignTimeDbContextFactory interface. It’s not necessary, we can quickly solve this issue by adding the following lines to our Program.cs file:

This function will build a webhost and load the Startup file. That way, when .NET Core builds the project it will know how to create an instance of the DBContext because it will be registered with the ASP.NET Core Dependency Injection Container

Note that attempting to call this method from inside Main will cause your Service Fabric build to fail because it will hijack the default port 5000. Doing so will cause any subsequent microservice build to fail.

Using the HttpClient the correct way

The other day I was building a small demo ASP.NET Core 2.0 application for the purposes of a video course I’m preparing on the upcoming second version of .NET Core.

The application was making several http requests to third party APIs. I noticed that it was taking unusually long to finish. At first I thought that something was wrong with the preview version of .NET Core and curious to find out why I ported it to the stable .NET Core 1.1 and started filling the code with stopwatches to discover the source of the lag.

What I found out was that I have been using the HttpClient all wrong. And probably so do you. All the countless C# books, tutorials and courses out there all mention that the correct usage of the HttpClient is withing a ”using’ statement.

The flow of this thought goes something like this: The HttpClient holds unmanaged resources, it also implement the IDisposable interface. When it comes to other IDisposables like the StreamReader we wrap them in ‘using’ statements so we should do the same with HttpClient.

The problem is, that’s not the case! Creating a new instance of the HttpClient every time we make a request and disposing it after the request completes is not the most sensible thing to do as it turns out. You’re better off having a single HttpClient instance. You can achieve this by creating a wrapper for the HttpClient and either declare it as static or register it as a singleton with your preferred IoC container. The second solution seems more elegant and avoids the static cling code smell.

But let’s take it from the beginning. After the discovering what made my application so slow, I figured I could run a test. So I created a .NET Core Console Applciation from scratch. I then went on to creating two classes, the SlowWay and the FastWay static classes. (I know, awful names). Both classes make several requests to this url: http://jsonplaceholder.typicode.com/photos.

The SlowWay classes follows the famous ‘using’ convention. The FastWay class uses the same HttpClient for all requests

And here’s how I tested them:

With the RequestCount set to 30 I got the following results:

blog1

The slow approach takes almost double the time, something that proves my fears about the ‘using’ statement

Increasing the RequestCount to 30 results in almost triple performance decrease:

blog2

Increasing to 60 got me even closer to 3 times increase in performance improvement when using the fast approach.

Imagine the performance increase that little modification can lead to in Microservices Oriented Applications.

After digging around the internet for quite some time I stumbled upon an awesome article that describes the source of the issue. Apparently, it’s a TCP socket issue. Check the article from ASP.NET Monsters for more information.

Oh and stop wrapping your HttpClients in ‘using’ statements when making multiple requests. I certainly will.

The whole project is available in this repo: https://github.com/dimlucas/HttpClientPerformanceTest

Overloading the indexer operator in C#

There’s a feature in C# that’s very useful for some use cases, yet many people seem to overlook it. I’m talking about the indexer operator. What this operator does is, it makes it possible to access elements of an enumerable data structure that your class makes use of, with the familiar [] operator.

Let’s say we have a class named Car:

Now let’s say that we have multiple cars, multiple instances of the class Car and that we want to organize them in a collection. What should we use? A plain old Generic List you might say and you would be correct, but what happens if we want to augment that list with more operations, more car-specific operations. Perhaps we want to clean the cars, or repair them. All that logic can nicely go inside a class named Garage:

As you can see we still use a List to store the cars, but we’re using the delegate pattern. A generic list has a bunch of methods but we only need three of them, the Add(), ElementAt() and Remove() methods. Oh and we also need the Count property so that we know how many cars we have.

This is an initial draft of our garage class showing the use of the delegate pattern. We can also include other stuff to make the class resemble real-life garage even more

The addition of the Clean() and Repair() methods improves our Garage implementation but there’s something missing. Every time we want to access a specific car by index we are forced to use the Get() method. It’s counter-intuitive. Here’s where the powerful indexer operator comes into play. After we’ve implemented an indexer operator in our collection class we will be able to access car elements with array-like syntax, like this:

Let’s see how simple it is to do that

So basically, you override the indexer operator like a property, with a getter and a setter. In this particular example we don’t want to be able to manipulate the contents of the garage so we don’t need a setter. But using a setter is a totally legitimate operation and one you will probably find pretty helpful once you start using it. That’s how easy it is 🙂

Check the whole project on this GitHub repo

The proper way to dynamically create a two-dimensional array in C

When I began working with matrices in C, I was obsessed with malloc. I almost never defined static arrays, because I thought that malloc turned me into a ‘Memory God’ capable of managing memory efficiently and improving loading and response times of my application, all while not putting the burden on the operating system. So, I quickly figured out how to dynamically allocate a two dimensional array. This is what I used to do in order to create a 10×5 array of integers:

After the job was done, I used to free the matrix like this:

Someone might ask: “What’s wrong with that?”. Well, for most intents and purposes this code works perfectly fine, but there is one subtle issue with this code and chances are that, if you use something like that, you are not even aware of it. The problem with this code is that it goes against the way C allocates static matrices in memory.

When you create a static 3×3 matrix in C like this:

int staticMatrix[3][3];

the memory blocks allocated for each column stand each next to each other as demonstrated below:

2darr1

The green blocks are the columns of the first row, the red blocks are the columns of the second row and the purple blocks are the columns of the third row. This two-dimensional array or array of arrays is actually a contiguous block in memory.

This is also the reason why the second dimension is always required when passing a 2D array to a functionË™ the compiler needs to now the offset between rows, because in memory there are no actual dimensions. To better explain this, let’s assume you have this function that takes a 2D array and does some operations on it (we do not care about the exact operations):

void workWithMatrix(int matrix[][3]);

We are required to specify the number of columns, but not the number of rows (although we can include that too, if we want). That’s because, every time we use the indexer operator, the compiler translates our statement into a pointer. If the following statement exists within workWithMatrix:

int value = matrix[2][1];

The compiler will “translate it” to this:

int value = *(matrix + 2*3 + 1);  //*(matrix + 7)
[\c]

If the statement was:


int value = matrix[1][1];
[\c]

It would translate into this:


int value = *(matrix + 1*3 + 1);  //*(matrix + 4)

Notice the number 3, that’s the offset, a.k.a. the number of columns, a.k.a. the number of blocks between two rows.

This is a visual illustration of how the compiler treats your 2D array as a single dimension one.

2darr2

The following is a typical illustration of how the dynamic matrix we created with malloc gets stored in memory:

2darr3

As you can see, the blocks may be consecutive or they may not, there is no guarantee. That rarely causes a problem in most C programs, but when you have some advance logic, you want the matrix to be stored in contiguous blocks (for example, when creating a derived data type in MPI). To fix this, let’s introduce the correct way to dynamically allocate two dimensional arrays. What we want is to emulate a static array and from what we’ve seen, a statically defined 2D array is actually a one dimensional array (since there’s no such thing as a dimension in memory). So, when we want an NxM matrix, we first need to create a one dimensional array containing NxM elements, and then we create an array of pointers and make them point to the correct place in memory.

In the following example, N=3 and M=3.

In steps:

 

1. Create a one-dimensional array of 3×3=9 elements: 
2darr4

2. Create a one-dimensional array of N=3 pointers (equal to the number of rows):
2darr5

3. Loop through the array of pointers and make them point to the start of each row, first one to array[0], second one to array[3] and the third one to array[6]:
2darr6

4. Use the array of pointers (which is an int** for integers, a float** for floats, etc.) to reference the elements using the indexer operator []

 
And the long awaited code to achieve the above:

After we’re done with the matrix, we need to free any memory associated with it. To do that, we need to use a different approach than just looping through the rows and freeing the columns. This approach is actually faster and simpler. Straight to the code:

Remember that matrix[0] is an array in and of itself. So we just need to free that, and also free the array of pointers. Pretty simple stuff.

I’ve also included some more helper functions for matrix operations. You can check them out here

I hope you liked this post and found it helpful. Have a nice day!

Loose Coupling in C# Explained

Hello everyone, in this tutorial I want to provide you with a simple as possible, yet comprehensive enough example of what loose coupling really is and why it’s useful. Understand loose coupling and you’re going to have another advanced software engineering concept under your belt.

Before we start, I’m going to borrow the Loose Coupling definition from Wikipedia:
In computing and systems design a loosely coupled system is one in which each of its components has, or makes use of, little or no knowledge of the definitions of other separate components. Sub-areas include the coupling of classes, interfaces, data, and services.

The key takeaway from this is the phrase “little to no knowledge”. Object oriented programming and design offers multiple layers of abstraction for your application. That’s another key-word, “Abstraction”. Everyone who has ever taken a course on OOP or read an OOP book has stumbled upon this word and probably knows how OOP helps you achieve Polymorphism. The benefits of loose coupling include:

• Cleaner Code: After applying loose coupling your code is going to be much easier to read
• More Maintainable Code: Your code will also be easier to change
• Testable Code: This is the reason why beginners see no need for loose coupling. Because most beginners do not unit test and don’t know how hard it is to unit test tightly coupled code
• Scalable Code: I understand that in a small application loose coupling might not make any noticeable difference but in large scale projects it just makes your life a lot easier

The easiest way to explain loose coupling is actually to explain the exact opposite, tight coupling. Tight coupling is when one or more classes in your application is highly dependent on one or more other classes. Take this class hierarchy for example:

class ClassA
{
    public ClassA() { }
}

class ClassB
{
    public ClassB()
    {
        _foo = new ClassA();
    }

    private ClassA _foo;
}

In this simple example, ClassB contains an instance of ClassA and ClassB is responsible for creating that instance. So in this implementation ClassB needs to have knowledge about the inner workings of ClassA. Remember that we want ClassB to have little or no knowledge about how ClassA operates or how its objects get instantiated. The above code using loose coupling will look like this:

class ClassA : IMyInterface
{
    public ClassA() {  }
}

class ClassB
{
    public ClassB(IMyInterface foo)
    {
        _foo = foo;
    }

    private IMyInterface _foo;
}

An interface, in this very simplistic example called MyInterface, is introduced to solve the conflict. That way, any class that implements IMyInterface can be passed to class B who no longer needs to know how to instantiate it.

To provide a more real-world example, I will create a Console Application project with some rather simple functionality. It’s going to display some to-dos in the console and whether those To-Dos have been completed or not. (The full code of this project can be found here).

I’m going to create a “Models” folder to place my ToDo class first:

I tried to keep it as simple as possible, after all this is just a console application.

Next let’s create the class with the basic to-do functionality. For the sake of demonstration I’m going to actually create two classes. One will be tight coupled, the other will be loosely coupled. Let’s name them TightlyCoupledToDos and LooselyCoupledToDos respectively.

For now the two classes are essentially identical:

public class TightlyCoupledToDos
{
    public class TightlyCoupledToDos
    {
        
    }

    public async Task<IEnumerable<ToDo>> All()
    {

    }
}
public class LooselyCoupledToDos
{
    public LooselyCoupledToDos()
    {

    {

    public IEnumerable<ToDo> All()
    {

    }
}

Both have an All() method that returns a list of to-dos. The interesting part in how these two classes are going to populate the to-do list. In a real world application data like that probably come from a service. So let’s go ahead and create our ToDoService in a ‘Services’ folder:

public class ToDoService
{
    public IEnumerable<ToDo> GetAll()
    {
    	
    }
}

This is an initial form of the service. Because we don’t have an API or a database we are going to fetch data from JSONPlaceholder’s ToDo list which can be found here https://jsonplaceholder.typicode.com/todos

To parse the JSON data we will use Newtonsoft’s NuGet package. To add it:
• Right click on your project
• Go to ‘Manage NuGet Packages’
• Go to the ‘Browse’ tab
• Search for ‘Newtonsoft.Json’
• Click Install

Next we will use an HttpClient and the Newtonsoft.JsonConvert class to get the data from the API and parse them to a list of ToDo objects:

A simple enough, service implementation. It uses an instance of the HttpClient class to asynchronously read JSON data the feed them to the Json Converter for deserialization.

After having created the service, let’s use it in our TightlyCoupledToDos class to get some data.

You see the service in initialized in the constructor and the All() method uses the service to get the parsed data and return it

Let’s go in our Program.cs file to make use of the TightlyCoupledToDos class and display the list of to-dos on screen

class Program
{
    static void Main(string[] args)
    {
        ToDos();
        Console.ReadLine();
    }

    static async void ToDos()
    {
        TightlyCoupledToDOs vm = new TightlyCoupledToDos();
        IEnumerable<ToDo> todos = await vm.all();
        foreach(ToDo todo in todos)
        {
            Console.WriteLine(todo);
        }
    }
}

The Console.ReadLine() statement is there to keep the console window open for us, so that we can see the results. The ToDos() method instantiates the TightlyCoupledToDos class, gets the todos asynchronously and writes them to the output:

loosecoupling

So far so good, our classes all work and the absence of loose coupling has yet to come back and bite us. But what if we need to use another service. There are several reasons why we would want to replace the ToDoService with something else:
• We might want to test our code with fake data provided by fake service
• We might want to support different sources of data like files, APIs or databases
• We might want to conditionally supply a service to the ToDos class according to some event

It’s hard to do so when the ToDos class heavily depends on a specific service implementation. As you might have guessed it’s time to get ourselves some loose coupling. Here’s what we need to do:

• Create a IToDoService interface that will be implemented by any supporting service
• Modify our ToDoService to implement the IToDoService interface
• Create a TestToDoService that also implements IToDoService
• Modify LooselyCoupledToDos to work with either service

The implementation of the IToDoService is pretty simple:

And in ToDoService:

Now let’s create another service that will return local data to the caller instead of calling an API or querying a database. This is a rather common practice during unit tests.

The TestToDoService implements the IToDoService differently. Instead of using an HttpClient to get JSON data from the web, this class creates a list and fills it up with some dummy data to be sent to the caller for testing

Now this is the most important step of them all! We need to go to our LooselyCoupledToDos class and make it support what its name says it supports. In order to do that, the class needs to hold a reference to an IToDoService object and not a ToDoService or TestToDoService object. It also needs to take that reference as a constructor argument rather than instantiating on its own. That way our LooselyCoupledToDo class knows nothing about the actual service and thus we will have achieved the precious separation of concerns we want.

Now that we’ve implemented our classes in a loosely coupled way let’s see how easy it is to switch services. Let’s introduce a static field in our Program class that will be true if the app is in test mode and therefore needs to use test data or false if the application is not in test mode and must fetch real data:

If _testMode is true the LooselyCoupledToDos is initialized with the test service, if it is not it gets initialized with the real service.

You can see the whole project in my GitHub repository dedicated to C# here

Now that you’ve learned what loose coupling is, it’s time to take it one step further and learn about Inversion Of Control and Dependency Injection. I will be writing on those soon. Until then, keep coding!!

The secret of C one-dimensional arrays

One thing that confuses newcomers to the C language, whÎż usually are newcomers to programming altogether, is the distinction between pointers and arrays. When you start learning C, you first learn about arrays. Every book or course teaches you statically allocated one dimensional arrays first. A statically allocated array is declared like this:

int array[10]; //Declares an array of 10 integers

One thing that confuses newcomers to the C language, whÎż usually are newcomers to programming altogether, is the distinction between pointers and arrays. When you start learning C, you first learn about arrays. Every book or course teaches you statically allocated one dimensional arrays first. A statically allocated array is declared like this:

int* dynamicArray= malloc(8*sizeof(int));

Let’s dissect the above statement. We have a pointer to an integer (array). If you’ve studied pointers, you know very well that a pointer to an integer is actually an integer itself that contains the address of an integer in memory. What happens next is that we use the malloc function that allocates memory for 10 integers on another memory segment, the heap. A ‘stack vs heaps argument’ could have an article on its own, but for now let’s just focus on the key difference between the two, which is the fact that everything that’s put on the stack lives as long as the function that created it lives. When that functions’ job is done, it gets kicked out of the stack and so are any variables, arrays or structures that were defined within it. On the contrary, everything allocated on the heap lives as long as the whole program lives in memory, unless we explicitly free that part of the memory. That’s another essential part of dynamic arrays that we are usually taughtË™ when we’re done with them we should ‘free’ them:

free(dynamicArray);   //Any memory that was used for this array now belongs to the operating system to utilize

The first question that popped into my mind when I started learning that stuff was: “How the hell can I tell the difference between a pointer to a single integer and a dynamically allocated array of who-knows-how-many integers?”

The missing piece of the puzzle was a small bit of information about arrays:
The name of the array (a.k.a the variable) is a pointer to the first element of the array.

Sounds confusing? Let me explain. The variable that you use to handle the array, like ‘dynamicArray’ in the above example, is actually a pointer to the first element of the array. Let’s say that our dynamicArray contains the following integers: 6,4,5,7,9,1,0,2

arr1

So we can get the first element just by dereferencing the pointer:

printf("First element = %d\n", (*dynamicArray));

Now, what about the second element? We can get that by moving the pointer one position to the right:

printf("Second element = %d\n", *(dynamicArray + 1));

The third element by moving two positions to the right:

printf("Third element = %d\n", *(dynamicArray + 2));

etc…

This sounds similar to the zero-based indexing of a statically declared array. If we wanted to get the first element of the array, we statically defined in the beginning of this article we would use this syntax:

int firstElement = array[0];

When you first learn about the zero-based index everyone tells you “that’s the way it is” and you’re left wondering why this:

int firstElement = array[0];

Is better than this:

int firstElement = array[1];

Now you know the reason why. It’s because the variable name points to the first element. And guess what, this applies to statically defined arrays too!

You see, the ‘dereference method’ of accessing array elements is not exclusive to arrays created using malloc. You can use it in plain old statically defined arrays too! Because the ‘array’ variable we used above is also a pointer. To better explain this, I’ve put together a small console application that shows that you can use both the indexing operator ( [] ) and the pointer dereference operator ( * ) with any array, whether statically or dynamically defined:

We start by defining two identical one dimensional arrays, the first one on the stack and the second one on the heap. We then go on and print the first and fifth element of each array using both methods, therefore proving that both methods can be used regardless of the way the array has been defined.

How to pass arrays as arguments

Now that we’ve dug deeper in the world of one dimensional arrays, let’s see how we can pass them around functions. To do that, let’s write a ‘printArr’ function that will print the contents of a one-dimensional array.

For a function to print an array, it needs to know two things: the array (duh) and its size. So we need a function that will take two arguments and since it won’t return anything, it can be void. So we have the function’s signature!

void printArr(int array[], int size);

The ‘[]’ syntax tells the compiler that this function expects its first argument to be an array.

Here’s the implementation. Nothing fancy, just a loop over the array contents and a call to printf

Now let’s use it to print the two arrays we defined earlier:

printf("Array contents:\n");
printf(array, 8);

printf("dynamicArray contents:\n");
printArr(dynamicArray, 8);

The results are:

arr_results

Which is correct, of course.

There is also another way to pass an array to a function. Instead of using the [] syntax, we could just pass a pointer since every array is actually a pointer to the first element!There is also another way to pass an array to a function. Instead of using the [] syntax, we could just pass a pointer since every array is actually a pointer to the first element!

There is also another way to pass an array to a function. Instead of using the [] syntax, we could just pass a pointer since every array is actually a pointer to the first element!

printf("Array contents (alternative method):\n");
altPrintArr(array, 8);

printf("dynamicArray contents (alternative method):\n");
altPrintArr(dynamicArray, 8);

What should I use

Okay, so, we learned that there are two ways to access an arrays’ content and there also are two ways to pass an array to a function. But which one should I use? Well, when it comes to accessing array elements, I personally believe that using the indexer operator makes your code cleaner, nicer and more comprehensible. As far as argument passing is concerned, someone might say that the pointer approach can get confusing when someone else reads your code because there is no immediate way of telling if the function accepts a pointer to a single element or an array.

It all comes down to personal preference though. I personally prefer using the indexing operator for accessing elements and I like using the pointer syntax for array arguments.

Conclusion

That was it! I hope you found this article helpful in your quest to master not only one-dimensional arrays, but C in general. The rest of the code can be found on GitHub. More stuff on C coming up soon. Thanks for reading. Keep coding!!

Post-order Traversal of a Binary Tree in C++

If you know about pre-order traversal you know that it visits the root first and the subtrees later. If you know about in-order traversal you know that it visits the nodes in-order (duh), first the left subtree , then the root and finally the right subtree. The remaining combination is to operate on the root when you’re done with the subtrees. That’s what post-order traversal does.

Let’s see an example of printing all the nodes of a tree using post-order traversal:

binarytree

Starting from the root the post-order traversal algorithm will visit the left subtree, the right subtree and then return to the root node when it’s done.

Output so far:

We visit the left subtree on node-9 and move on its own subtrees until we find the tree’s leaves.

Output so far:

When we reach node-2 there are no left and right subtrees so we print it

Output so far: 2

Same way with node-5

Output so far: 2, 5

We return to node-9 and since we’re done with its subtrees we print the value 9

Output so far: 2, 5, 9

Back to node-6. We haven’t yet visited its right subtree so on we go

Output so far: 2, 5, 9

Node-4 has no left subtree, so we visit its right-hand one.

Output so far: 2, 5, 9

We visit node-8’s left and right subtrees which are empty and then return to node-8 and print its value

Output so far: 2, 5, 9, 8

Now that we’re done with node-4’s subtrees we print its value

Output so far: 2, 5, 9, 8, 4

We’re done with both subtrees of our tree’s root, node-6. It’s time to print its value too.

Output so far: 2, 5, 9, 8, 4, 6

And that’s it. We’ve traversed the tree In a post-order fashion and have printed its nodes.

The algorithm that achieves that in C++ is the following:

In-order Traversal of a Binary Tree in C++

In-order traversal is probably the most widely used type of tree traversal algorithm mainly because when applied to Binary Search Trees it can operate on the nodes in order (duh!). The in-order traversal algorithm first operates on the left subtree, returns on the root operates on it and then traverses the right subtree.

To demonstrate the algorithm we’re going to print the integer values of a binary tree whose nodes are described by the following struct:

An unconventional and not very scientific way to think about the algorithm is that it visits nodes in this order:

  1. Left
  2. Middle
  3. Right

It helps if you’re trying to visualize it. Speaking of visualization let’s see an example of the algorithm in action. We have the following binary tree:

binarytree

Starting from root-node 6, the algorithm will check if the node is NULL and since it is not, it will visit its left subtree first, then it will return print 6 and visit the right subtree.

Output so far:

We are at node 9, the start of node-6 left subtree. The node is not NULL so the algorithm goes deeper to the next left subtree

Output so far:

Node 2, also not null. The algorithm goes to the left again

Output so far:

We’ve bumped into NULL, the function returns control to the caller. So we’re back at node 2. We print it

Output so far: 2

Now it’s time for the right subtree. We visit it, find out it’s NULL and then return to node-2. Node-2 is done so back to node-9

Output so far: 2

We’re done with node-9’s left sub tree so we print 9 and head over to its right subtree

Output so far: 2, 9

We’re at node-5, it’s not NULL so we go to its left subtree which is NULL so we return to node-5, print 5 and move to the right subtree which is also non-existent so we go back to node-9

Output so far: 2, 9, 5

We’ve printed node-9’s left subtree, its own value and its right subtree so we’re done and return to node-6. We print 6 and move to the right subtree

Output so far: 2, 9, 5, 6

We are at node-4 which is not NULL so we visit its left sub-tree

Output so far: 2, 9, 5, 6

Node-4’s left subtree does not exist so we return to node-4 and print its value

Output so far: 2, 9, 5, 6, 4

Next, we visit node-4’s right subtree at node-8

Output so far: 2, 9, 5, 6, 4

Node-8 is not NULL so we visit its left subtree. Node-8’s left subtree is NULL so we return to node-8 print its value and visit its right subtree

Output so far: 2, 9, 5, 6, 4, 8

Nothing here so back to node-8. But we’re done with node-8 so back to node-4. Node-4 is also finished, so back to the root. The root is also finished so we’re done.

Final Output: 2, 9, 5, 6, 4, 8

Here’s the code of in-order traversal in C++ :