Binary Tree : Non recursive routine to print ancestor of a node in a Binary Tree?

Question

I have to write a non recursive program to print the ancestor (parent of parent) of a given node in a Binary Tree. What logic should I use ?

Answer 1

Use a non recursive sub routine to traverse the binary tree( refer to http://en.wikipedia.org/wiki/Tree_traversal#Implementations) and maintain a stack to store the all parent nodes in that array and whenever you pop from stack suitably pop the element from the stack. Finally when you find the element, second topmost element on the stack would be the ancestor.

Answer 2

Use any of the iterative implementations listed here and stop when you reach the grandparent node (node.Left.Left = desired OR node.Left.Right = desired OR node.Right.Left = desired OR node.Right.Right = desired). You'll obviously first need to test that a candidate node does indeed have grandchildren.

Answer 3

You can just do a standard tree walk and remember the last two steps, like a limited stack. The below fragment uses an array[2] of pointers to remember the last two steps (Note: "opa" is Dutch for "granddad"):

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

struct tree_node {
    struct tree_node * left;
    struct tree_node * right;
    int data;
};

        /* a bonsai-tree for testing */
struct tree_node nodes[10] =
/* 0 */ {{ nodes+1, nodes+2, 10}
/* 1 */ ,{ nodes+3, nodes+4, 5}
/* 2 */ ,{ nodes+5, nodes+6, 17}
/* 3 */ ,{ nodes+7, nodes+8, 3}
/* 4 */ ,{ nodes+9, NULL, 7}
/* 5 */ ,{ NULL, NULL, 14}
/* 6 */ ,{ NULL, NULL, 18}
/* 7 */ ,{ NULL, NULL, 1}
/* 8 */ ,{ NULL, NULL, 4}
        };

struct tree_node * find_opa(struct tree_node *ptr, int val)
{
struct tree_node *array[2] = {NULL,NULL};
unsigned step=0;

for (step=0; ptr; step++) {
        if (ptr->data == val) break;
        array[ step % 2] = ptr;
        ptr = (val < ptr->data) ? ptr->left : ptr->right;
        }

return ptr ? array[step %2] : NULL;
}

void show(struct tree_node *ptr, int indent)
{
if (!ptr) { printf("Null\n"); return; }

printf("Node(%d):\n", ptr->data);
printf("%*c=", indent, 'L');  show (ptr->left, indent+2);
printf("%*c=", indent, 'R');  show (ptr->right, indent+2);
}

int main(void)
{
struct tree_node *root, *opa;

root = nodes;
show (root, 0);

opa = find_opa(root, 4);
printf("Opa(4)=:\n" );
show (opa, 0);
return 0;
}