c++ - BST in array transversal -

i have following implementation of binary tree in array;

   32   /  \  2    -5      /  \    -331   399 

the data grouped 3 indexes @ time. index%3==0 value of node, index%3==1 index of value of left node , index%3==2 index of value of right node. if left or right index reference 0, there no node direction.

i'm trying find depth (height) of tree. i've written recursively

height(node):     if node == null:         return 0    else:         return max(height(node.l), height(node.r)) + 1 

i want find non-recursive solution, however.

here pseudocode have, assuming tree not empty

int = 0; int left = 0; int right = 0; while (i != n ){ if ( a[i+1] != 0 ){   left++; } else if ( a[i+2] != 0 ){   right++; }  = + 3;  }  return max ( left, right ) + 1; 

i don't think right , i'd figuring out how correctly.

you haven't said problem recursion understand behavior want improve.

there many solutions this, of them have same or worse performance recursive solution. really, best solutions going things you'd have when you're creating tree. example, store height of each node in fourth array index per node. it's trivial scan of every fourth index find max height. make easier if nodes had parent references stored them didn't have computed during height check.

one solution simulate recursion stack, that's no different recursion.

another solution go through each node , determine height based on it's parent, not in specific traversal's order. however, because of how have configured, without secondary datastructure store hierarchy, it's going less efficient o(n^2). problem can't child parent without full array scan. can in linear time (but recursion linear time, i'm not sure we're doing better. it's not going better memory perspective).

can define type of efficiency want improve?

here's pseudocode each, i'm depending on few datastructures aren't present:

"recursion without recursion" solution:

int get_height(int * tree, int length) {      stack stack;      int max_height = 0;      if (length == 0) {         return 0;     }      // push "array" of node index process , height of parent.       //   make struct , use real c code     stack.push(0,0);      while(!stack.empty()) {         int node_index, parent_height = stack.pop();          int height = parent_height + 1;         if (height > max_height) {             max_height=height;         }         if (tree[node_index+1] != 0 )             stack.push(tree[node_index+1], height);         if (tree[node_index+2] != 0 )             stack.push(tree[node_index+2], height);      }      return max_height; } 

now working on slow solution uses no additional memory, it's bad. it's writing fibonacci recursively bad. original algorithm went through each node , performed o(n) checks worst case runtime of o(n^2) (actually not quite bad had thought)

edit: later i'm adding optimization skips nodes children. important, cuts out lot of calls. best case if tree linked list, in case runs in o(n) time. worst case balanced tree - logn leaf nodes each doing logn checks root o((log(n)^2). isn't bad. lines below marked such

"really slow no memory" solution (but updated not slow):

int get_height(int * tree, int length) {     int max_height = 0;     (int = 0; < length; i+=3) {          // optimization added later         // if node has children, can't tallest node, don't         //   bother checking here, child checked         if (tree[i+1] != 0 || tree[i+2] != 0)             continue;          int height = 0;         int index_pointing_at_me;          // while haven't gotten head of tree, keep working         while (index_pointing_at_me != 0) {             height += 1;              (int j = 0; j < length; j+=3) {                 if (tree[j+1] == tree[i] ||                     tree[j+2] == tree[i]) {                     index_pointing_at_me = j;                     break;                 }             }          }         if (height > max_height) {             max_height = height;         }      }      return max_height; } 

improved on previous solution, uses o(n) memory - assumes parents before children in array (which suppose isn't technically required)

int get_height(int * tree, int length) {      if (length == 0)          return 0;      // 2 more nodes per node - 1 node parent, other height     int * reverse_mapping = malloc((sizeof(int) * length / 3) * 2)      reverse_mapping[1] = 1; // set height 1 first node        // make mapping each node node points it.     // example, first node     //    a[0] = 32     //    a[1] = 3     //    a[2] = 6     //  store node @ 3 , 6 both pointed node 0 (divide 3 saves space since 1 value needed) , each child node 1 taller parent     int max_height = 0;     (int = 0; < length; i+=3) {          int current_height = reverse_mapping[(i/3)*2+1];         if (current_height > max_height)             max_height = current_height;          reverse_mapping[(tree[i+1]/3)*2] = i;         reverse_mapping[(tree[i+1]/3)*2 + 1] = current_height + 1;          reverse_mapping[(tree[i+2]/3)*2] = i;         reverse_mapping[(tree[i+2]/3)*2 + 1] = current_height + 1;      }     return max_height }