Height of a Binary Tree: Recursion Unrolled & Explained

Posted on by Vishal

—
tags: >-
development, C++, tree, height, programming, recursion, internals, complete
flow
categories: development

—

Height of a Binary Tree is the longest path in the tree.

Code
int getHeight(node *root)
{
    if (root == NULL) {
        return -1;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);

    return (max(leftHeight, rightHeight) + 1);     
}

Suppose the tree is as follows:

         [10]
          |
       [8]  [12]
              |
           [4] [5]

The recursion flow is as following:

1. getHeight(10)
2. getHeight(left of 10) ==> getHeight(8)
3. getHeight(left of 8) ==> getHeight(NULL)
4. getHeight(NULL) returns -1
5. leftHeight = -1 and flow goes back to line # 3
6. Now, it calls right of 8, getHeight(right of 8)
7. getHeight(NULL) returns -1 to rHeight
8. Both subtree of 8 are traversed and leftHeight = -1, rightHeight = -1
9. It compares both values and return the max + 1
10. max( -1, -1) + 1 = 0
11. The node 8 is left subtree of 10, and returns to line # 2.
12. At node 10, leftHeight = 0
13. Now, rightHeight is calculated by moving to right of 10.
14. getHeight(right of 10) ==> getHeight(12)
15. Similar to above, height at node 12 is calculated as 1.
16. At the end, node 12 returns its height at line #14.
17. Again we compare max (0, 1) + 1
18. The answer is 2
Summary

Usually, all recursion steps are not visualized and just assumed to be working. This post tries to exhaust a recursion flow and help understand it better.

Advertisements

File system in userspace (FUSE) on Linux : C implementation

Posted on by Vishal
  • BBFS is a good starting point to develop a file system in C
  • Application should keep in mind file offset before issuing a request. A write should be followed with a seek to offset zero, before issuing read.
  • FUSE 2.7 reads 8K data by default, in two 4K chunks
  • Read happens in last 4K and the first 4K data block

Example:

I had set the file size as 4MB in getattr () implementation.

int bb_getattr(const char *path, struct stat *statbuf)
{
    int retstat = 0;
    char fpath[PATH_MAX];
    bb_fullpath(fpath, path);

    memset(statbuf, 0, sizeof(struct stat));
    if (strcmp(path, "/") == 0) {
        statbuf->st_mode = S_IFDIR | 0755;
        statbuf->st_nlink = 2;
    } else {
        statbuf->st_mode = S_IFREG | 0444;
        statbuf->st_nlink = 1;
        statbuf->st_size = 4 * 1024* 1024;
    }   
    return retstat;
}

The sequence of calls and their arguments is as follows:

bb_getattr(path="/abcd.txt", statbuf=0xc5387960)
    bb_fullpath:  rootdir = "/tmp", path = "/abcd.txt", fpath = "/tmp/abcd.txt"
bb_open(path"/abcd.txt", fi=0xc5daaa50)
    bb_fullpath:  rootdir = "/tmp", path = "/abcd.txt", fpath = "/tmp/abcd.txt"
    fi:
    flags = 0x00008002
    fh_old = 0x00000000
    writepage = 0
    direct_io = 0
    keep_cache = 0
    fh = 0x0000000000000001
    lock_owner = 0x0000000000000000
bb_write(path="/abcd.txt", buf=0xc4966050, size=10, offset=0, fi=0xc5387a50)
    fi:
    flags = 0x00000000
    fh_old = 0x00000001
    writepage = 0
    direct_io = 0
    keep_cache = 0
    fh = 0x0000000000000001
    lock_owner = 0x0000000000000000
bb_read(path="/abcd.txt", buf=0x06ccbd90, size=12288, offset=4096, fi=0xc5daaa50)  <- Here
    fi:
    flags = 0x00000000
    fh_old = 0x00000001
    writepage = 0
    direct_io = 0
    keep_cache = 0
    fh = 0x0000000000000001
    lock_owner = 0x0000000000000000

bb_read(path="/abcd.txt", buf=0x06ccbd90, size=4096, offset=0, fi=0xc5daaa50)
    fi:
    flags = 0x00000000
    fh_old = 0x00000001
    writepage = 0
    direct_io = 0
    keep_cache = 0
    fh = 0x0000000000000001
    lock_owner = 0x0000000000000000

Forward declaration of a structure in C

Posted on by Vishal

What do you think of following code?

/*
 * decl.h
 */
struct junk {
    int a;
};

----------------------------------------------
/*
 * fwd.c
 * We have not included the header file decl.h.
 */
#include 
struct junk;

int main()
{
    struct junk *ptr;
    printf("%d", ptr->a);
}

You will get compilation error that structure object ptr is incomplete. This is misleading if you do not go through all included header files. cscope will make you believe that definition exists. You just wonder till you find out that structure was never defined in fwd.c!

GNU gdb for C++ applications

Posted on by Vishal

For C programmers, using GDB for C++ applications could be daunting task. I have learned following lessons:

    • Always pass fully qualified name of a function such as namespace_1::class_1::function1
    • You can’t put a breakpoint on a template function.
jango::IndexInterface<jango::treedata_v1>::toIndex
      • The easiest way is to put the breakpoint on the line number of the template function.
    • C++ application’s core is legible if you interpret it ignoring name mangling of functions.
_ZN5ns_111class_a6functionB2EPKcPKvibbbPb+0x15ca 
 ==> ns::class_a::functionB()

Headless link list implementation in C

Posted on by Vishal

Singly link list

A link list is a non-linear data structure with a head pointer. The rest of the nodes in the list could be accessed by using “next” of head.

The code to create a list of N node involves creating head separately. Rest of the nodes are appended to the head.

That looked ugly to me and so I wrote it in a generic manner. Using a temporary pointer, I wrote a single loop to create N link list nodes, keeping head intact.

Here is the code:

#define NULL (char*)0

typedef struct node_ {
        int n;
        struct node_ *next;
} node;

int main()
{
        int i = 5;
        node *head = NULL;
        node *temp = NULL;

        while (i-- > 0) {
                head = malloc(sizeof(node));
                head->n = i;
                head->next = temp;
                temp = head;
        }

        temp = head;

Pitfall of C array

Posted on by Vishal

CODE

int main()
{
int my_array[4] = {11,12,13,14};
int next = 15;
printf("\nSurprise = %d", my_array[4]);
}

What should it print?

Well, although illegal, the above code does legal things. The array “my_array” has four integers allocated on the stack. The next integer “next” is allocated adjacent to the stack memory. So the address of “next” would be (my_array + 5).


-----------------------
11| 12| 13| 14| 15|
-----------------------
^
|
The memory layout on stack is linear and hence our array and the integer are adjacent to each other.

It is a subtle error and you should know it.

Synchronize two threads to print ordered even and odd numbers in C

Posted on by Vishal

Problem:You have two threads, that independently print even and odd values. The goal is to synchronize these threads so as to get an non-decreasing ordered set of numbers and order should preserve natural ordering of numbers. So the output should be 1,2,3,4,5,6,7,8…..

It is an interesting problem and could be solved with a conditional variable.

Following is C implementation of the solution:

#include "stdio.h"
#include "stdlib.h"
#include "pthread.h"

pthread_mutex_t count_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t condition_var = PTHREAD_COND_INITIALIZER;
void *functionCount1();
void *functionCount2();
int count = 0;
#define COUNT_DONE 200

void main()
{
 pthread_t thread1, thread2;
 pthread_create( &thread1, NULL, &functionCount1, NULL);
 pthread_create( &thread2, NULL, &functionCount2, NULL);
 pthread_join( thread1, NULL);
 pthread_join( thread2, NULL);
 exit(0);
}

// Print odd numbers
void *functionCount1()
{
  for(;;) {
   // Lock mutex and then wait for signal to relase mutex
   pthread_mutex_lock( &count_mutex );
   if ( count % 2 != 0 ) {
     pthread_cond_wait( &condition_var, &count_mutex );
   }
   count++;
   printf("Counter value functionCount1: %d\n",count);
   pthread_cond_signal( &condition_var );
   if ( count >= COUNT_DONE ) {
     pthread_mutex_unlock( &count_mutex );
     return(NULL);
   }
   pthread_mutex_unlock( &count_mutex );
 }
}

// print even numbers
void *functionCount2()
{
  for(;;) {
  // Lock mutex and then wait for signal to relase mutex
  pthread_mutex_lock( &count_mutex );
  if ( count % 2 == 0 ) {
    pthread_cond_wait( &condition_var, &count_mutex );
  }
  count++;
  printf("Counter value functionCount2: %d\n",count);
  pthread_cond_signal( &condition_var );
  if( count >= COUNT_DONE ) {
    pthread_mutex_unlock( &count_mutex );
    return(NULL);
  }
  pthread_mutex_unlock( &count_mutex );
 }
}

Python goof ups of a C/C++ programmer

Posted on by Vishal

Python is a new age language when compared to good old C. Writing code in Python needs a subtle shift from C mindset. Python offers so many things ready-made that make you feel that you wrote very less code. Anyway, I goofed up while using a very common feature of C: pass by reference.

Python too offers it, but with a caveat: you should know mutable and immutable data objects. When you pass a mutable object like list, dictionary; they can be changed. But, if you pass an immutable data object like string, tuple; they are kept unchanged in caller’s scope. This is very similar to passing “references” (C++) or constant pointers.

  1 class Node:
  2     def __init__(self, value, data=[]):
  3         self.char = value
  4         # We intend to keep a list of values for a key
  5         self.data = data
  6         # XXX: List of Node
  7         self.children = []
  8
  9
 10 n = Node('a')
 11 m = Node('b')
 12
 13 (n.data).append("north")
 14 (m.data).append("south")
 15
 16 print n.data
 17 print m.data

The output of the above code is:

ubuntu@ubuntu:~/Desktop/ToKeep/cprogs/pycon$ python pybug.py
['north', 'south']
['north', 'south']

I don’t quite understand why Python keeps a single instance of default argument(list). Nonetheless, it is interesting.

This thread on Stackoverflow is very informational.

  • Omitting “this” pointer

In C++, “this” which is pointer to the object is passed implicitly. Python has similar keyword “self” for this. But, contrary to an implicit understanding, “self” should be an argument to a function, else you would see an error:

NameError: global name ‘self’ is not defined

  1 class pydbg:
  2     def __init__(self, modname=None):
  3         self.level = 0
  4         self.modname = modname
  5
  6     def DLOG(self, lvl=None, fmt=None, *args):
  7         self.level = lvl
  8         print '%s' %self.modname
  9         print fmt
 10         for arg in args:
 11             print arg

So, always add the “self” argument while adding a function in your class.

Potential pitfall of ‘new’ operator in C++: Missing ‘NULL’

Posted on by Vishal

I faced a very interesting problem in a C++ code. The code logic was as follows:

#include<stdio.h>

int main()
{

int *p = new int();
int* B[10];

for ( int i =0; i<10; i++)
{
delete p;
//p = NULL;
printf(“Address1 =  %x\n”, p);

int *q = new int();
printf(“Address2 =  %x\n”, q);

B[i] = q;

i++;
}

}

Output:

kanaujia@ubuntu:~/Desktop/ToKeep/cprogs$ ./a.out
Address1 =  96f8008
Address2 =  96f8008
Address1 =  96f8008
Address2 =  96f8008
Address1 =  96f8008
Address2 =  96f8008
Address1 =  96f8008
Address2 =  96f8008
Address1 =  96f8008
Address2 =  96f8008

This code looks pretty simple and with no bug, right? But, it has an interesting problem. The first memory allocation of integer will give us an address from the heap (say, it is 0x12345).

Now inside the loop, with first iteration, we free this memory. ‘new’ will mark this address 0x12345 in free-list. Next , we again ask an integer memory allocation. And ‘new’ returned me same address 0x12345 for this allocation. I save this address in array B. Next and henceforth forth iterations will call ‘delete’ on 0x12345, and again ask an allocation. This request again returns 0x12345. So, we end up with single value of 0x12345 for *all* elements of arrayB.

How to fix this:

Always mark the pointer to NULL after calling ‘delete’. Just mark p as NULL here.

9         for ( int i =0; i<10; i++)
10         {
11                 delete p;
12                 p = NULL;
13                 printf(“Address1 =  %x\n”, p);
14
15                 int *q = new int();
16                 printf(“Address2 =  %x\n”, q);
17
18                 B[i] = q;
19
20                 i++;
21         }

Output:

kanaujia@ubuntu:~/Desktop/ToKeep/cprogs$ ./a.out
Address1 =  0
Address2 =  9265008
Address1 =  0
Address2 =  9265018
Address1 =  0
Address2 =  9265028
Address1 =  0
Address2 =  9265038
Address1 =  0
Address2 =  9265048

That’s it folks! Hope you enjoyed it.

Unfolding 2-D array in C

Posted on by Vishal

Last weekend my friends and I had a discussion on 2-D array in C. Surprisingly it went long as everyone had some points and knowledge to share 🙂 Finally we could gather some important information and understood this pearl of C better.

I’ll clear this idea with C code snippets.

// Declare an array
int arr[2][3]= {1,2,3,4,5,6};

It’s size is 2*3*sizeof(int) = 24 bytes (Intel x86)

okay, now what will get printed for following statements:
// Say starting address is 1024

o) print &a + 1
o) print a + 1
o) print *a + 1

To answer these questions better, I’ll explain what exactly is a 2-D array. When we declare and define a 2-D array, it’s like a new user defined type to C. It’s a pointer to a memory location that contiguously contains storage of 6 integers. Logically it’s like holding many 1-D array in a followed by one-another.

Ans 1: When you say ‘&a’ , it implies address of user defined type and it’s 1024. Now incrementing it by 1 means moving the pointer by the size of this type which is 24 bytes. Thus it’ll print 1048.

Ans 2: ‘a’ fetch us address of 1-D array or 0th row of our matrix. a+1 would get us address of next row i.e. 1024 + (3*4) = 1036

Ans 3: ‘*a’ would get you the 0th element of 0th row which is 1. So *a + 1 would get us 2.