Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node {
int value;
struct node *left;
struct node *right;
} node;
int depth(node *tree) {
if (!tree)
return 0;
int l = depth(tree->left);
int r = depth(tree->right);
return 1 + (l > r ? l : r);
}
int depth2(node *tree) {
int retval;
int l;
int r;
if (!tree) {
retval = 0;
return retval;
}
l = depth(tree->left);
r = depth(tree->right);
retval = 1 + (l > r ? l : r);
return retval;
}
typedef struct depth_stack {
int l;
int r;
node *tree;
int resume_point;
struct depth_stack *parent;
int retval;
int returned_val;
} depth_stack;
int depth3(node *tree) {
depth_stack *pStack = malloc(sizeof(depth_stack));
pStack->parent = NULL;
pStack->tree = tree;
if (!pStack->tree) {
pStack->retval = 0;
return pStack->retval;
}
pStack->l = depth(pStack->tree->left);
pStack->r = depth(pStack->tree->right);
pStack->retval = 1 + (pStack->l > pStack->r ? pStack->l : pStack->r);
return pStack->retval;
}
int depth4(node *tree) {
depth_stack *tmp_stack = malloc(sizeof(depth_stack));
tmp_stack->tree = tree;
depth_stack *pStack = NULL;
push:
tmp_stack->parent = pStack;
pStack = tmp_stack;
if (!pStack->tree) {
pStack->retval = 0;
goto pop;
}
// Recurse left call
pStack->resume_point = 1; // will pick up back here
tmp_stack = malloc(sizeof(depth_stack));
*tmp_stack = *pStack;
tmp_stack->tree = pStack->tree->left;
goto push;
recur1done:
pStack->l = pStack->returned_val;
// Recurse right call
pStack->resume_point = 2; // will pick up back here
tmp_stack = malloc(sizeof(depth_stack));
*tmp_stack = *pStack;
tmp_stack->tree = pStack->tree->right;
goto push;
recur2done:
pStack->r = pStack->returned_val;
pStack->retval = 1 + (pStack->l > pStack->r ? pStack->l : pStack->r);
goto pop;
pop:
if (pStack->parent) {
tmp_stack = pStack;
pStack = tmp_stack->parent;
pStack->returned_val = tmp_stack->retval;
free(tmp_stack);
if (pStack->resume_point == 1) goto recur1done;
if (pStack->resume_point == 2) goto recur2done;
}
return pStack->retval;
}
int main()
{
node *myTree = calloc(1, sizeof(*myTree));
for (int i = 1; i < 150; ++i) {
node *newTree = calloc(1, sizeof(*newTree));
newTree->left = myTree;
myTree = newTree;
}
printf("%d\n", depth(myTree));
printf("%d\n", depth2(myTree));
printf("%d\n", depth3(myTree));
printf("%d\n", depth4(myTree));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment