Binary Search Tree algorithm which returns an array of value within a range

Question

Write a recursive range function that given a binary search tree, two integers k1 and k2 such that k1 ≤ k2 and a vector v, inserts in v all the keys in ascending order organized in the tree such that k1 ≤ k ≤ k2 . The function returns the size of the vector v.

This is my solution:

typedef struct node {
  int key;
  struct node * left;
  struct node * right;
  struct node * parent;
} * Node;

void rangeRic(Node u, int k1, int k2, int v[], int * pindex) {
  if (u == NULL) {
    return;
  }

  rangeRic(u->left,k1,k2,v,pindex);

  if (u->key >= k1 && u->key <= k2) {
    v[*pindex] = u->key;
    *pindex += 1;
  }

  rangeRic(u->right,k1,k2,v,pindex);
}

int range(Node u, int k1, int k2, int v[]) {
  int i = 0;
  rangeRic(u,k1,k2,v,&i);
  return i;
}

My problem is that the exercise description also states the following:

You cannot use any auxiliary function and the vector v has enough space to contain all the elements that satisfy the condition.

and this last statement invalidates my solution.

How to compile: gcc -std=gnu89 -pedantic -Wall -o main main.c binarySearchTree.c

Could you guys help me with this ?

How Node is defined? Why is there used Node u instead of Node *u? — Vlad from Moscow, Nov 01 '19 at 14:23
Maybe make `i` a [`static`](https://stackoverflow.com/q/572547/669576) variable in `range()`. Remember to reset to 0 before returning for subsequent calls to `range()`. — 001, Nov 01 '19 at 14:24
@JohnnyMopp my code above works, the problem is I cannot use any auxiliary function, so I need to find a different solution. — ddon-90, Nov 01 '19 at 14:28
@ElDon90 I understand that. It seems the main reason you have `rangeRic` function is because of the `pindex` parameter. If you make `i` static, you can move the code from `rangeRic` into `range` and get rid of the `rangeRic` function. (The `i` variable will replace the `*pindex` variable). — 001, Nov 01 '19 at 14:31
And you have posted ALL requirements? There's absolutely nothing in the instructions that you have forgotten to mention? — klutt, Nov 01 '19 at 14:31
@klutt I can only add that I compile my code as follows: `gcc -std=gnu89 -pedantic -Wall -o main main.c binarySearchTree.c` — ddon-90, Nov 01 '19 at 14:42
@JohnnyMopp Thanks, that works. I am only wondering if there is another way to achieve this. Maybe using a different approach/algorithm. — ddon-90, Nov 01 '19 at 14:44
1) you don't need the `parent` pointer, 2) you don't need the `pindex` argument (use the return value and the `v[]` argument instead) — joop, Nov 01 '19 at 14:50
Something in my head tells me that I can solve the problem by handling the way I return the array dimension after each recursive call, I am not sure if I explained myself properly. — ddon-90, Nov 01 '19 at 14:50
@joop I was thinking something like that. The parent is used for others things outside the scope of this post. — ddon-90, Nov 01 '19 at 14:51
(remember: arrays are passed as pointers) I think you've had enough hints now... — joop, Nov 01 '19 at 14:53

001 · Accepted Answer · 2019-11-01T15:55:44.283

2

You can return how many items have been added from each node and use that as the index into the array.

int range(Node u, int k1, int k2, int v[]) {
  if (u == NULL) {
    return 0;
  }

  // Will return how many items added from the left side
  int count = range(u->left, k1, k2, v);

  if (u->key >= k1 && u->key <= k2) {
    // Add and increment counter
    v[count++] = u->key;
  }

  // Add how many from the right side
  // Note: passing the last part of the array
  // Could also write v+count as &v[count]
  return count + range(u->right, k1, k2, v + count);
}

edited Nov 01 '19 at 15:55

answered Nov 01 '19 at 15:05

001

13,291
5
35
66

The function should also return the the array dimension `int range(Node u, int k1, int k2, int v[])` – ddon-90 Nov 01 '19 at 15:09
@ElDon90 Glad it works. Just made a test app and it seems to work ok (https://ideone.com/Yvhzoo). Note that I did away with the pointer typedef. I am not a fan of hiding pointers like that. See [the first comment on your post for why](https://stackoverflow.com/questions/58660778/binary-search-tree-algorithm-which-returns-an-array-of-value-within-a-range/58661471?#comment103624857_58660778) – 001 Nov 01 '19 at 15:52
Neither am I, I agree with you but my hands are tied since the tree implementation is given as part of this exercise. – ddon-90 Nov 01 '19 at 16:01

Binary Search Tree algorithm which returns an array of value within a range

1 Answers1