How to count amount of leafes in binary tree without recursion in C?

Question

I need to make a function to count the amount of leafes of a binary tree and prints the highest and lowest value, for this homework I can't use recursivity so I'm struggling to figure out how to do it. The structure is:

typedef struct node {
  int value;
  struct node *left;
  struct node *right;
} Node ;

To insert a node I created a function

void insert(Node** tree, int value){
  if(*tree== NULL){
    *tree= createNode(value);
  } else {
    int sValue= (*tree)->value;
    if(value < sValue){
      insert(&(*tree)->left, value);
    } else {
      insert(&(*tree)->right, value);
    }
  }
}

Node* createNode(int value){
  Node* newNode= (Node*)malloc(sizeof(Node));
  newNode->value= value;
  newNode->left= NULL;
  newNode->left= NULL;
  return newNode;
}

The answer to [this question](https://stackoverflow.com/questions/62392275/should-i-avoid-recursion-everywhere-its-possible) may help — ForceBru, Jun 15 '20 at 21:12
Like others said, you'll need a second structure to keep track of nodes that you need to explore. [Here](https://stackoverflow.com/questions/13466800/how-can-i-get-number-of-leaf-nodes-in-binary-tree-non-recursively) is an example that uses a stack, that should give you an idea of what your solution looks like. — AJ_, Jun 15 '20 at 21:28

score 1 · Answer 1 · answered Jun 15 '20 at 22:41

Traversing a tree without recursion is usually done using a stack data structure, usually one that dynamically grows and shrinks (since you do not know the number of nodes in your tree in advance).

A different approach would be to use a list "currentNodes" of non-leaf-nodes of one level, and iterate this to build a list "nextLevelNodes" of non-leaf-noded of the next level. This avoids a dynamically growing stack data structure:

void printLeafsNonRecursive(Node *tree) {

    // the current level starts with one (root) node:
    Node **currentLevel = calloc(sizeof(Node*),1);
    currentLevel[0] = tree;
    int nodesAdded = 1; 

    while (nodesAdded) {
        unsigned maxNodes = nodesAdded * 2;
        Node **nextLevel = calloc(sizeof(Node*),maxNodes);
        int nextLevelNodeCount = 0;
        for (int i=0; i<nodesAdded; i++) {
            Node *node = currentLevel[i];
            if (node->left == NULL && node->right == NULL) {
                printf("%d\n",node->value);
            } else {
                if (node->left) {
                    nextLevel[nextLevelNodeCount++] = node->left;
                }
                if (node->right) {
                    nextLevel[nextLevelNodeCount++] = node->right;
                }
            }
        }
        nodesAdded = nextLevelNodeCount;
        free(currentLevel);
        currentLevel = nextLevel;
    }
    free(currentLevel);
}

This is very helpful, thank you so much but when I tried it sometimes shows two numbers and other times only one. Maybe I did something wrong, Can you explain how it works? — RaCo, Jun 15 '20 at 23:23

How to count amount of leafes in binary tree without recursion in C?

1 Answers1