Thread: 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);
        }

}

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 =(

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