1. ## 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.

2. 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)?

3. 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);
}

}```

4. 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

5. 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.

6. 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("&#37;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]\$```

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

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

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.

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;
}```
Code:
```BTREE findRightMostLeaf(BTREE root)
{
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?

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