Binary tree - print leaf-to-leaf path [C]

Question

I'm trying to do my homework but I'm having some difficult.

Create a recursive function who prints the path between a leaf to another in an integer binary tree (i.e. the tree holds integers).

int printPath(Tree* t, int a, int b).

Note: You will have to handle the following situations:

• there's no a and/or b in the tree. if so, return -1.

• If there are, print all the values between the node whose value a and the node whose value b. return 0.

I tried this code:

int print1(Tree* tree, int a, int b) {
    int cnt;
    int c = MAX(a, b), d = MIN(a, b);
    a = d;
    b = c;
    if (!tree)
        return -1;
    /*
     if (tree->key.id > b || tree->key.id < a) {
         if(tree->key.id > b)
             cnt = print(tree->left, a, b);
         else
             cnt = print(tree->right, a, b);
     }*/

    if (tree->key.id == a || tree->key.id == b) {
        if (tree->key.HWGrade) {
            printf("e) , %d -> ", tree->key.id);
            tree->key.HWGrade = 0;
        }
        return 0;
    }

    if (tree->key.id > b) {
        cnt = print1(tree->left, a, b);
        if (tree->key.HWGrade) {
            printf("c) , %d -> ", tree->key.id);
            tree->key.HWGrade = 0;
        } else
            return 0;
    } else {
        if (tree->key.id > a) {
            cnt = print1(tree->left, a, b);
            if (tree->key.id != a && tree->key.id != b && !cnt) {

                if (tree->key.HWGrade) {
                    printf("d) , %d -> ", tree->key.id);
                    tree->key.HWGrade = 0;
                } else
                    return 0;
            }
        }
    }

    if (tree->key.id < a) {
        cnt = print1(tree->right, a, b);
        if (tree->key.id != a && tree->key.id != b && !cnt) {
            if (tree->key.HWGrade) {
                printf("a) , %d -> ", tree->key.id);
                tree->key.HWGrade = 0;
            } else
                return 0;
        }
    } else {
        if (tree->key.id < b) {
            cnt = print1(tree->right, a, b);
            if (tree->key.id != a && tree->key.id != b && !cnt) {
                if (tree->key.HWGrade) {
                    printf("b) , %d -> ", tree->key.id);
                    tree->key.HWGrade = 0;
                } else
                    return 0;
            }
        }
    }

    if (cnt == 0)
        return 0;
    return -1;
}

But it doesn't seem to work.

Structure who's been used:

typedef struct {
    int id;
    int HWGrade;
    int ExamGrade;
} MatamStudent;

typedef struct Tree{
    int Data;
    struct Link* list;
    MatamStudent key;
    struct Tree *left;
    struct Tree *right;
} Tree;

I'm using GCC with Eclipse under Ubuntu.

Answer 1

The way you search for the node in a balanced tree will correspond with the way that you insert the node; if you have a recursive function to insert a new value, then you already have the code to find it :)

Here's an example for finding; deriving the code to print the path is left as an exercise to the student :)

Points to note

there are four possibilites in every leaf: 1) the leaf is the one you're searching for 2) the leaf on the left has an id lower than the leaf you're searching for, and the key will be a child of that leaf 3) the leaf on the right has an id greater than the leaf you're searching for 4) there are no more leaves and the value doesn't exist.

Your code is much more complicated than it need be. A tree structure can have an arbitrary set of properties, but it must have a root leef. A leaf structure need only have 3 properties (it can have more, but doesn't have to): it needs 2 (for a binary tree) pointers to children, and it needs a key. If you have more data than that, you are making this harder than it is. Here's an interesting challenge for you-add the print code without modifying the search code; seperation of concerns, programming bread and butter :)

Node* find_child(Node* parent, int id)
{
    if (parent->id == id)
        return parent;
    else if (parent->left.id < id)
        return find_child(parent->left, id);
    else if(parent->right.id < id)
        return find_child(parent->right, id)
    else
        return NULL;
}

Good luck, I hope this helps. :)

Answer 2

I don't see where your array it is said that your tree has to be sorted. An intuitive algorithm could be:

• Search a and save the path from the root to this node in p1 (of size n).
• Search b and save the path from the root to this node in p2 (of size m).
• Compare the two paths. When two values p1[i] and p2[i] are different, you can travel p1 from p1[m] to p1[i], and the second path from p2[i] to p[m].

The algorithm runs in O(S), where S is the number of leaves.

#include <stdio.h>

size_t mid, i;
int p1[MAX_LEAVES];
int p2[MAX_LEAVES];
int n = searchTree(p1, tree, a);
int m = searchTree(p2, tree, b);

if (n == 0 || m == 0)
    return -1;

for (mid = 0; mid < n && mid < m && p1[mid] == p2[mid]; mid++)
    ;

for (i = n - 1; i >= mid; i--)
    printf("%d ", p1[i]);

for (i = mid; i < m; i++)
    printf("%d ", p2[i]);

putchar('\n');

return 0;