Binary Tree and It's Traversal

A tree is called a binary tree where each node has zero, one, or two children ie. at most 2 children.

There are three different methods for traversing binary trees: preorder, postorder and in-order.

Preorder
preorder: Current node, left subtree, right subtree

preorder(node)
    visit(node)
    if node.left != null then preorder(node.left)
    if node.right != null then preorder(node.right)

Postorder
postorder: Left subtree, right subtree, current node

postorder(node)
    if node.left != null then postorder(node.left)
    if node.right != null then postorder(node.right)
    visit(node)

Inorder
in-order: Left subtree, current node, right subtree

inorder(node)
    if node.left != null then inorder(node.left)
    visit(node)
    if node.right != null then inorder(node.right)

Example

If we have a tree as shown above, then the output for different traversal method will be as:
1. preorder : 50, 30, 20, 40, 90, 100
2. postorder : 20, 40, 30, 100, 90, 50
3. inorder : 20, 30, 40, 50, 90, 100

Creating a shared library in linux

Lets discuss how to create a shared library in linux and use it in another program.

Step 1. Write the header and source file that will be used to create the shared library. We'll call them myclass.h and myclass.cc.

myclass.h

#ifndef __MYCLASS_H__
#define __MYCLASS_H__

class myClass
{
public:
    myClass() {}

    // use virtual otherwise linker will try to perform static linkage.
    virtual void myFunction();
};

#endif // __MYCLASS_H__

myclass.cc

#include <iostream>
#include "myclass.h"

using namespace std;

void myClass::myFunction()
{
   cout<<"Hello from shared library.\n";
}

Step 2. Creating Object File with Position Independent Code

The code that constitutes the shared library needs to be position independent. Because since several programs can use a single instance of your shared library the location of that library in memory will vary from program to program. PIC works no matter where in memory it is placed.

g++ -c -fpic myclass.cc -o myclass.o

Compiler options:
-c : Here our objective is to create the object file and not to run the linker. The "-c" oprtion is used to achive this.

-fpic : It generate position-independent code(PIC) suitable for use in a shared library. PIC accesses all constant addresses through a global offset table(GOT). The dynamic loader(part of the operating system) resolves the GOT entries when the program starts. If the GOT size for the linked executable exceeds a machine-specific maximum size, you get an error message from the linker indicating that -fpic does not work. For such case, recompile with "-fPIC" option. The "-fPIC" option avoids any limit on the size of the global offset table.

-o [filename]: Place output in file file named filename.

Step 3. Creating Shared library from the generated Object File

Now we will create a shared library using the object file created in previous step. We’ll call it libmyclass.so.

g++ -shared -o libmyclass.so myclass.o

Compiler options:
-shared: Produce a shared object which can then be linked with other objects to form an executable.

-o [libname] : create the shared object with libname. If not specified the will create shared library with default name i.e. "a.out".

In this step the shared library is created and ready for use. In the next step we will see how to use it.

Step 4. Using the Shared Library
Create a programme and link it with the above shared library. we'll call it test.cc.

test.cc

#include <iostream>
#include "myclass.h"

using namespace std;

int main()
{
    cout<<"This is a test program for shared library.\n";
    myClass m;
    m.myFunction();
}

Now link the program with the shared library:

g++ -o test test.cc -lmyclass -L/PATH-TO-LIBRARY

Compiler options:
-l [library]: Search the library named library when linking. It should be noted that the -lmyclass option is not looking for myclass.o, but liblmyclass.so.

-L[dir] : Add directory dir to the list of directories to be searched for library mentioned with option -l. Note that g++ first searches for libraries in /usr/local/lib, then in /usr/lib. Following that, it searches for libraries in the directories specified by the -L parameter.

What will happen if you don't provide the -L option? say you link the program as:

g++ -o test test.cc -lmyclass

It will throw the below error:

/usr/bin/ld: cannot find -lmyclass
collect2: ld returned 1 exit status

What will happen if you don't provide the -l option also? See it yourself.

Step 4. Run the program that uses the library

./test
./test: error while loading shared libraries: libmyclass.so: cannot open shared object file: No such file or directory

The problem is that the loader can’t find the shared library. since libmyclass.so is not present in a standard location used for library lookup, we need to set the environment variable LD_LIBRARY_PATH with the path that contans libmyclass.so .

export LD_LIBRARY_PATH=/PATH-TO-LIBRARY/:$LD_LIBRARY_PATH

Now run the program again. You will see the output as:

./test
This is a test program for shared library.
Hello from shared library.