Segment tree challenge Here is my implementation of a segment tree with a sample driver file (I didn't make an update function because I didn't need it for what I was doing).

I'm a huge fan of geeksforgeeks, but I do not understand why this link makes such a complicated implementation.  I didn't use the height or compute the maximum size in order to build mine. Not to mention, their structure really isn't a tree; it's an integer array.

I'm looking for what I implemented well and what I did not implement well.  

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

typedef struct segment_tree_node_s
{
  struct segment_tree_node_s * left;
  struct segment_tree_node_s * right;
  int start;
  int end;
  int sum;
} segment_tree_node_t;

typedef struct segment_tree_s
{
  segment_tree_node_t * root;
} segment_tree_t;

int build_tree(segment_tree_node_t **, int, int);
int query_tree(segment_tree_node_t *, int, int);

static const int ra[] = {1,3,5,7,9,11};
int main(int argc, char * argv[])
{
  segment_tree_t * new_tree = (segment_tree_t *) malloc(sizeof(segment_tree_t));
  int length = sizeof(ra)/sizeof(ra[0]);
  int sum = build_tree(&amp;new_tree-&gt;root, 0, length - 1);
  int sum_2 = query_tree(new_tree-&gt;root, 0, 0); 
  int sum_3 = query_tree(new_tree-&gt;root, 0, 1); 
  int sum_4 = query_tree(new_tree-&gt;root, 0, 2); 
  int sum_5 = query_tree(new_tree-&gt;root, 0, 3); 
  int sum_6 = query_tree(new_tree-&gt;root, 0, 4); 
  int sum_7 = query_tree(new_tree-&gt;root, 1, 5); 
  int sum_8 = query_tree(new_tree-&gt;root, 2, 4); 
  int sum_9 = query_tree(new_tree-&gt;root, 4, 5); 
  int sum_10 = query_tree(new_tree-&gt;root, 5, 5); 

  printf("Sum of tree [0-5]: %d\n", sum);
  printf("Sum of tree [0-0]: %d\n", sum_2);
  printf("Sum of tree [0-1]: %d\n", sum_3);
  printf("Sum of tree [0-2]: %d\n", sum_4);
  printf("Sum of tree [0-3]: %d\n", sum_5);
  printf("Sum of tree [0-4]: %d\n", sum_6);
  printf("Sum of tree [1-5]: %d\n", sum_7);
  printf("Sum of tree [2-4]: %d\n", sum_8);
  printf("Sum of tree [4-5]: %d\n", sum_9);
  printf("Sum of tree [5-5]: %d\n", sum_10);

  return 0;
}

int build_tree(segment_tree_node_t ** node, int start, int end)
{
  *node = (segment_tree_node_t *)malloc(sizeof(segment_tree_node_t));
  (*node)-&gt;sum = 0;

  if(start != end)
  {
    (*node)-&gt;start = start;
    (*node)-&gt;end   = end;
    int mid = start + (end - start)/2;
    return (*node)-&gt;sum = build_tree(&amp;((*node)-&gt;left), start, mid) + build_tree(&amp;((*node)-&gt;right), mid + 1, end);   
  }
  else
  {
    (*node)-&gt;start = start;
    (*node)-&gt;end   = end;
    (*node)-&gt;sum = ra[start];
    return ra[start];
  }
}

int query_tree(segment_tree_node_t * node, int start, int end)
{
    /* Total overlap */
    if(node-&gt;start &gt;= start &amp;&amp; node-&gt;start &lt;= end)
    {
        if(node-&gt;end &lt;= end &amp;&amp; node-&gt;end &gt;= start)
            return node-&gt;sum;
    }

    /* Partial overlap */
    if((start &gt;= node-&gt;start &amp;&amp; start &lt;= node-&gt;end) || (end &gt;= node-&gt;end &amp;&amp; end &lt;= node-&gt;start) || (start &lt;= node-&gt;start &amp;&amp; end &gt;= node-&gt;start))
            return query_tree(node-&gt;left, start, end) + query_tree(node-&gt;right, start, end);

    /* No overlap */
    return 0;
}
Bounds checking simplification

Your bounds checking code is overly complicated.  This total overlap check:


/* Total overlap */
if(node-&gt;start &gt;= start &amp;&amp; node-&gt;start &lt;= end)
{
    if(node-&gt;end &lt;= end &amp;&amp; node-&gt;end &gt;= start)
        return node-&gt;sum;
}



could be reduced to:

/* Total overlap */
if(node-&gt;start &gt;= start &amp;&amp; node-&gt;end &lt;= end)
{
    return node-&gt;sum;
}


In this partial overlap check:


/* Partial overlap */
if((start &gt;= node-&gt;start &amp;&amp; start &lt;= node-&gt;end) ||
       (end &gt;= node-&gt;end &amp;&amp; end &lt;= node-&gt;start) ||
       (start &lt;= node-&gt;start &amp;&amp; end &gt;= node-&gt;start))



I noticed that the second of the three conditions always evaluates to false.  Some of the other parts are also unnecessary.  In fact the whole thing could be rewritten as:

/* Partial overlap */
if (start &lt;= node-&gt;end &amp;&amp; end &gt;= node-&gt;start)


Use of globals

The function build_tree() references the array ra directly.  It would be better for that array to be passed in as an argument.  Otherwise that function can't be used for any other segment tree.