Binary Tree/Recursion

Hi, i'm trying to write a function to find the rightmost leaf node (a node with no children).

This is the code I have so far.

Code:

---

#include "tree.h"

void inorder(BTREE root);

int main()
{





        return 0;
}

void inorder(BTREE root)
{
        if (root != NULL)
        {
                inorder(root -> left);
                printf("%c ", root -> d);
                inorder(root -> right);
        }
}

/*BTREE findRightMostLeaf(BTREE root)
{
        if (root != NULL)
        {
                findRightMostLeaf(root -> right)
                if()
        }

}*/

void replaceWithRightmost(BTREE root)
{
        root = findRightMostLeaf(root);
}

---

in file tree.h

Code:

---

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

typedef  char  DATA;

struct node {
  DATA          d;
  struct node  *left;
  struct node  *right;
};

typedef  struct node  NODE;
typedef  NODE          *BTREE;

---

I can figure out how to solve this problem with a bunch of messy if statement/loop code, but I was looking for a recursive solution, similar to the function already defined in main.

Recursion is my weakness. Thanks for any help.

If I'm a leaf, return me (how do you check if I'm a leaf?)
if not, return a call to get the rightmost leaf of my right child.
if I don't have a right child, but I'm not a leaf, what do you do (special case)?

Very clever Perspective =)

How's this look?

Code:

---

BTREE findRightMostLeaf(BTREE root)
{
        if (root != NULL)
        {
                if((root -> left == NULL) && (root -> right)) //node is a leaf
                        return root;
                else if((root -> left != NULL) &&
                          (root -> right))          &&
                          (root -> left -> right != NULL))
                        return findRightMostLeaf(root -> left -> right);

                else
                        return findRightMostLeaf(root -> right);
        }

}

---

Your test seems a bit too complex - I'm pretty sure you don't need to do all those tests multiple times [you may get more if-statements, but as long as you don't repeat things in each if-statement, that's fine].

--
Mats

It looks like it wouldn't compile.
You should get some error along the lines of "Not all code paths return a value".

Your middle case is wrong, you're trying to skip a level of recursion. Just pass the left child. Afterall, you want it to work in a case like this right...

Code:

---

        H
    /      \
  B            M
              /
            L
            /
          J

---

Here the answer should be J.

Ok.. i'm getting there but i've hit a snag. When I print out the results, nothing comes out for the data of the switched node.

Here's the updated source..

ex32.c

Code:

---

#include "tree.h"

void inorder(BTREE root);
BTREE  create_tree(DATA a[], int i, int size);
void replaceWithRightmost(BTREE root);

int main()
{       
  BTREE  t;
  DATA    a[]  = "ABCDEFGHIK";
  int    size = 10;                                  /* size of a[] */

  t = create_tree(a, 0, size);
  replaceWithRightmost(t);

        return 0;
}

void inorder(BTREE root)
{
        if (root != NULL)
        {
                inorder(root -> left);
                printf("%c ", root -> d);
                inorder(root -> right);
        }
}

BTREE findRightMostLeaf(BTREE root)
{
        if (root != NULL)
        {
                if((root -> left == NULL) &&
                  (root -> right == NULL)) //it's a leaf
                        return root;
                else if((root -> right == NULL) &&
                        (root -> left != NULL))
                        return findRightMostLeaf(root -> left);
                else
                findRightMostLeaf(root -> right);               
        }
}

void replaceWithRightmost(BTREE root)
{
        printf("\n\n%c replaced with ", root -> d);
        root = findRightMostLeaf(root);
        printf("%c.\n\n", root -> d);
}

---

tree.h

Code:

---

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

typedef  char  DATA;

struct node {
  DATA          d;
  struct node  *left;
  struct node  *right;
};

typedef  struct node  NODE;
typedef  NODE          *BTREE;

/*
// Function prototypes.
*/

BTREE  create_tree(DATA a[], int i, int size);
BTREE  init_node(DATA d1, BTREE p1, BTREE p2);
BTREE  new_node(void);

void    inorder(BTREE root);
void    preorder(BTREE root);
void    postorder(BTREE root);

---

create.c

Code:

---

#include "tree.h"

/*
// Create a linked binary tree from an array.
*/

BTREE create_tree(DATA a[], int i, int size)
{
  if (i >= size)
      return NULL;
  else
      return (init_node(a[i],
                        create_tree(a, 2 * i + 1, size),
                        create_tree(a, 2 * i + 2, size)));
}

/*
// Initialize a node in a binary tree.
*/

BTREE init_node(DATA d1, BTREE p1, BTREE p2)
{
  BTREE  t;

  t = new_node();
  t -> d = d1;
  t -> left = p1;
  t -> right = p2;
  return t;
}

/*
// Create a new node.
*/

BTREE new_node(void)
{
  BTREE  t;

  t = (BTREE) malloc(sizeof(NODE));
  assert(t != NULL);
  return t;
}

---

Output:

Code:

---

[fl76a06@cisweb ex32]$ ./ex32


A replaced with
.

[fl76a06@cisweb ex32]$

---

*Bump* Plz help. This is due today =(

Error:

Quote:

---

Warning 2 warning C4715: 'findRightMostLeaf' : not all control paths return a value 42

---

Should probably return NULL if not found.

Code:

---

BTREE create_tree(DATA a[], int i, int size)
{
        if (i >= size)
                return NULL;
        else
                return (init_node(a[i],
                create_tree(a, 2 * i + 1, size),
                create_tree(a, 2 * i + 2, size)));
}

---

create_tree is misleading. It's actually PART of the if, but one can't be sure if it is or not.
I propose you put brackets around that else and indent create_tree (both lines) by one to signify it's a multiline command.
It's also very confusing - I would just use a hard-coded value or a loop or something. Very confusing.
Also just rewrite that function or get rid of it, because it's so very confusing. Create a tree a more normal way.

But insteado of:

Code:

---

BTREE findRightMostLeaf(BTREE root)
{
        if (root != NULL)
        {
                if((root -> left == NULL) &&
                        (root -> right == NULL)) //it's a leaf
                        return root;
                else if((root -> right == NULL) &&
                        (root -> left != NULL))
                        return findRightMostLeaf(root -> left);
                else
                        findRightMostLeaf(root -> right);               
        }
        return NULL;
}

---

How about just:

Code:

---

BTREE findRightMostLeaf(BTREE root)
{
        if (root == NULL) return NULL; /* Not found */
        if ( (root->left == NULL) && (root -> right == NULL) ) return root;
        if (root->right != NULL) return findRightMostLeaf(root->right); /* If the root->right isn't empty, then search it. */
        if (root->left != NULL) findRightMostLeaf(root->left);        /* Is root->left isn't empty, then search it */
        return NULL;
}

---

As for your bug... can it be something like:

Code:

---

BTREE findRightMostLeaf(BTREE root)
{
        if (root != NULL)
        {
                if((root -> left == NULL) &&
                        (root -> right == NULL)) //it's a leaf
                        return root;
                else if((root -> right == NULL) &&
                        (root -> left != NULL))
                        return findRightMostLeaf(root -> left);
                else
                        return findRightMostLeaf(root -> right);               
        }
        return NULL;
}

---

Perhaps?

YES!! Solved!! Thank you so much Elysia! The problem was the missing return statement. Sometimes I just need someone to look at my code.