Thread: How to iterate over a balanced binary tree in sequence? (inorder)

It's an interesting question. How to return a value-at-a-time from a recursive function? I don't see how it's directly possible.

The poor-man's way would be to read the tree data into an array first. Then a function with a static variable or two could serve the values from the array one at a time.

If you want to serve the data directly from the tree then you need to remove the recursion.

Take the following example:

Code:

void print_tree(Tree *t) {
    if (!t) return;
    print_tree(t->left);
    printf("%d\n", t->value);
    print_tree(t->right);
}

The second recursive call is tail-recursive and can be easily removed (compilers should do this automatically).

Code:

void print_tree(Tree *t) {
    while (t) {
        print_tree(t->left);
        printf("%d ", t->value);
        t = t->right;
    }
}

Now the hard part. You need to queue up the t->left calls.

Code:

// hide the ugly (poor-mans's) stack stuff
#define PUSH(x) do { \
            if (top >= STACK_SIZE) \
                err("stack overflow"); \
            st[top++] = x; } while(0)
#define POP() st[--top]
#define STACK_SIZE 100

void print_tree(Tree *t) {
    Tree *st[STACK_SIZE]; // or a dynamic stack-adt
    int top = 0;
    while (t) {
        if (t->left) {
            PUSH(t);
            t = t->left;
        }
        else {
            printf("%d ", t->value);
            t = t->right;
            while (!t && top > 0) {
                t = POP();
                printf("%d ", t->value);
                t = t->right;
            }
        }
    }
    printf("\n");
}

Then add in the needed statics and perchance a state variable and a goto or two. But maybe I'm overthinking this and there's a simpler way?

The iterator should contain a FIFO queue, which contains all the tree nodes visited, but not yet completely processed.

As you recurse to the left, you push that node onto the front of the queue.

As you unwind from the right, you pop that node off the front of the queue.

In what I consider to be a non-obvious solution, by modifying and restoring the links, then Morris traversal method can be used, which is an iterative (non-recursive) method to traverse a binary search tree in order. Example that traverses through an entire tree:

Inorder Tree Traversal without recursion and without stack! - GeeksforGeeks

I can later post example code for a function that takes a pointer to node as a parameter, and returns a pointer to the next in order node. After the initial call (using the root as the parameter), the caller calls the function with (previously_returned_pointer_to_node)->right to continue the in order traversal. Note that the entire tree needs to be traversed in order for all of the links to be restored.

Example code for program that manually creates a bst and then uses a Morris traversal function to return nodes one at a time. Note that main() advances to current_node->right in the for loop:

Code:

/* mrstrv.c - morris traversal of binary tree */
/* MorrisTraversal returns a set of pointers to nodes */

#include<stdio.h>
#include<stdlib.h>

/* binary tree node */
typedef struct BTNODE_
{
    struct BTNODE_* left;
    struct BTNODE_* right;
    int data;
}BTNODE;

/* traverse binary tree without stack */
/* initial input parameter is pointer to root */
/* predecessor of cur is largest value < cur */
/* predecessor of cur = cur->left->right->right->right ... */
BTNODE * MorrisTraversal(BTNODE *cur)
{
BTNODE *pre;
    if(cur == NULL)
        return(NULL);
    while(cur != NULL){
        /* if left end of branch, return */
        if(cur->left == NULL)
            return(cur);
        /* advance pre to predecessor of cur */
        pre = cur->left;
        while(pre->right != NULL && pre->right != cur)
            pre = pre->right;
        /* if right end of branch, change pre->right = cur */
        /*  and advance cur left */
        if(pre->right == NULL){
            pre->right = cur;
            cur = cur->left;
        /* else back at cur, so restore pre->right = NULL */
        /*  and return */
        } else {
            pre->right = NULL;
            return(cur);
        }
    }
    return(NULL);
}

BTNODE* newbtNode(int data)
{
BTNODE* btNode = (BTNODE*) malloc(sizeof(BTNODE));
    btNode->left = NULL;
    btNode->right = NULL;
    btNode->data = data;
    return(btNode);
}

int main()
{
BTNODE *root;
BTNODE *cur;
    /* manually create 15 element bst */
    root                      = newbtNode( 8);
    root->left                = newbtNode( 4);
    root->left->left          = newbtNode( 2);
    root->left->left->left    = newbtNode( 1);
    root->left->left->right   = newbtNode( 3);
    root->left->right         = newbtNode( 6);
    root->left->right->left   = newbtNode( 5);
    root->left->right->right  = newbtNode( 7);
    root->right               = newbtNode(12);
    root->right->left         = newbtNode(10);
    root->right->left->left   = newbtNode( 9);
    root->right->left->right  = newbtNode(11);
    root->right->right        = newbtNode(14);
    root->right->right->left  = newbtNode(13);
    root->right->right->right = newbtNode(15);
    /* use Morris traversal function to iterate through the tree */
    for(cur = root; cur; cur = cur->right){
        cur = MorrisTraversal(cur);
        printf("%2d ", cur->data);
    }
    return 0;
}

May as well show the beast I came up with. Not as clever as Morris. Uses a stack. I put both algorithms below, added a tree-displaying algorithm and random tree generation. Give a number at the command line to get a random tree of that size (start with 20). 0 or no number uses a 15-node balanced tree.

The tree is printed sideways, like this:

Code:

            .---97
            :   '---95
            :       '---83
        .---83
        :   '---81
        :       '---80
        :           '---78
    .---76
+---75
    :       .---73
    :   .---67
    :   :   :   .---65
    :   :   '---58
    :   :       '---55
    '---54
        :               .---52
        :           .---50
        :       .---46
        :       :   :   .---44
        :       :   :   :   '---42
        :       :   '---41
        :       :       :   .---38
        :       :       '---29
        :   .---22
        :   :   :   .---20
        :   :   '---14
        '---12
            :   .---6
            :   :   '---4
            '---1

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define MAX_STACK_SIZE 100  // for Iterator stack
#define MAX_PATH_DEPTH 100  // for printTreeStructure
 
typedef struct BTNODE_ {
    int data;
    struct BTNODE_ *left, *right;
} BTNODE;
 
typedef struct Iterator {
    int top;
    BTNODE *st[MAX_STACK_SIZE];
} Iterator;
 
 
BTNODE* MorrisTraversal (BTNODE *cur);
BTNODE* UT5000First     (BTNODE *t, Iterator *it);
BTNODE* UT5000Next      (Iterator *it);
BTNODE* newbtNode       (int data);
void    insert          (BTNODE **pt, int data);
void    printTree       (BTNODE *t);
void    err             (const char *msg);
 
 
int main(int argc, char **argv) {
    int size = 0;
    if (argc > 1) {
        size = atoi(argv[1]);
        if (size < 0) size = 0;
    }

    BTNODE *root = NULL;
    if (size > 0) {
        srand(time(NULL));
        for (int i = 0; i < size; i++)
            insert(&root, rand() % 100);
    }
    else {
        int a[] = {8,4,2,1,3,6,5,7,12,10,9,11,14,13,15};
        for (size_t i = 0; i < sizeof a / sizeof *a; i++)
            insert(&root, a[i]);
    }
 
    printTree(root);
 
    for(BTNODE *cur = root; cur; cur = cur->right){
        cur = MorrisTraversal(cur);
        printf("%2d ", cur->data);
    }
    printf("\n");
 
    Iterator it;
    BTNODE *nd = UT5000First(root, &it);
    while (nd) {
        printf("%2d ", nd->data);
        nd = UT5000Next(&it);
    }
    printf("\n");
 
    return 0;
}
 
 
void err(const char *msg) {
    fprintf(stderr, "Error: %s\n", msg);
    exit(EXIT_FAILURE);
}
 
 
BTNODE* newbtNode(int data) {
    BTNODE* btNode = malloc(sizeof *btNode);
    btNode->left = btNode->right = NULL;
    btNode->data = data;
    return btNode;
}
 
void insert(BTNODE **pt, int data) {
    for (BTNODE *t; (t = *pt) != NULL; )
        pt = data < t->data ? &t->left : &t->right;
    *pt = newbtNode(data);
}
 
 
void printTree(BTNODE *t) {
    static int depth = 0;
    static char path[MAX_PATH_DEPTH];
 
    if (!t) return;
 
    if (t->right) {
        if (depth == MAX_PATH_DEPTH) err("MAX_PATH_DEPTH");
        path[depth++] = 1;
        printTree(t->right);
        --depth;
    }
 
    for (int i = 0; i < depth; i++)
        printf("%c   ", i == 0 || path[i] == path[i - 1] ? ' ' : ':');
    printf("%c---%d\n",
        depth == 0 ? '+' : path[depth-1] ? '.' : '\'', t->data);
 
    if (t->left) {
        if (depth == MAX_PATH_DEPTH) err("MAX_PATH_DEPTH");
        path[depth++] = 0;
        printTree(t->left);
        --depth;
    }
}
 
 
//// MorrisTraversal //////////////////////////////////
 
BTNODE *MorrisTraversal(BTNODE *cur) {
    while (cur && cur->left){
        BTNODE *pre = cur->left;
        while (pre->right && pre->right != cur)
            pre = pre->right;
        if (!pre->right) {
            pre->right = cur;
            cur = cur->left;
        } else {
            pre->right = NULL;
            return cur;
        }
    }
    return cur;
}
 
 
//// UltraTraverse5000 ////////////////////////////////
 
BTNODE *UT5000First(BTNODE *t, Iterator *it) {
    if (!t) return NULL;
    it->top = 0;
    for ( ; t->left; t = t->left) it->st[it->top++] = t;
    return it->st[it->top] = t;
}
 
BTNODE *UT5000Next(Iterator *it) {
    BTNODE *t = it->st[it->top];
    if (!(t = t->right) && it->top)
        t = it->st[--it->top];
    else
        for ( ; t && t->left; t = t->left)
            it->st[it->top++] = t;
    return it->st[it->top] = t;
}