7 Replies - 1771 Views - Last Post: 10 August 2012 - 11:11 AM Rate Topic: -----

#1 MitulP91  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 64
  • Joined: 18-July 12

Recursion and Binary Search Trees

Posted 09 August 2012 - 02:04 PM

Hello everyone. Before I start off I'm aware of the rules where you are not meant to give me code. I'm not asking for code, but rather a step in the right direction. Just a point to start from.

I've been given an assignment to create a recursive algorithm that takes only a pointer r to the root of a binary tree and checks if the tree is a binary search tree. I don't actually need to make the tree, just this function.

The function call should look like this:

bool check(Node * r);



and the included struct is:

struct Node
{
    int     key;
    Node  * left;
    Node  * right;
};



I simply don't know how to go about doing this. Any hints would be much appreciated.

Is This A Good Question/Topic? 0
  • +

Replies To: Recursion and Binary Search Trees

#2 MitulP91  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 64
  • Joined: 18-July 12

Re: Recursion and Binary Search Trees

Posted 09 August 2012 - 02:22 PM

This is what I managed to put together. Look right to anyone?

bool check(Node * r)
{
	if (r == NULL)
	{
		return true;
	}

	if ((r->left != NULL) && (r->right != NULL))
	{
		if ((r->key > r->left->key) && (r->key < r->right->key))
		{
			return true;
			check(r->left);
			check(r->right);
		}
	}
	else
	{
		return false;
	}
}


Was This Post Helpful? 0
  • +
  • -

#3 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3576
  • View blog
  • Posts: 11,125
  • Joined: 05-May 12

Re: Recursion and Binary Search Trees

Posted 09 August 2012 - 02:57 PM

Line 12 prevents line 13 and 14 from executing. You probably want to check the results returned by the children and make decision based whether both children are also binary search trees.

You are making the assumption that all lesser values go to the left, and all greater values go to the right. What if the tree maker wanted things the other direction?

Also, you are making the assumption that it is binary search tree only if every node has two children, or is a leaf. A binary search tree can be sparse, or lopsided.

You are on the right track, though of breaking the problem down to subtrees.

This post has been edited by Skydiver: 09 August 2012 - 02:56 PM

Was This Post Helpful? 0
  • +
  • -

#4 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1346
  • View blog
  • Posts: 4,638
  • Joined: 19-February 09

Re: Recursion and Binary Search Trees

Posted 09 August 2012 - 02:58 PM

I think one branch can be null.

Binary search tree
Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5833
  • View blog
  • Posts: 12,687
  • Joined: 16-October 07

Re: Recursion and Binary Search Trees

Posted 10 August 2012 - 04:11 AM

Interesting. Your check for left and right should be independent.
if (r->left!=NULL) {
	if (r->key < r->left->key) { return false; }
	//...
}

if (r->right!=NULL) {



I don't believe allowing for different tree directions is within the scope of your problem. It it were, you function sig would be different. Stick with the one you're using for now.
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3576
  • View blog
  • Posts: 11,125
  • Joined: 05-May 12

Re: Recursion and Binary Search Trees

Posted 10 August 2012 - 10:41 AM

Assuming that lesser values always go the left child is like assuming that everybody drives on the right side of the road, or everybody uses the metric system.

Edit: fixed typo.

This post has been edited by Skydiver: 10 August 2012 - 11:08 AM

Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5833
  • View blog
  • Posts: 12,687
  • Joined: 16-October 07

Re: Recursion and Binary Search Trees

Posted 10 August 2012 - 11:01 AM

Yeah, I'm an ugly American, sue me. ;)

I agree, for a useful tree you'd really want a standard compare. Ideally you'd implement an operator override on less than somewhere. Or pass some compare interface. However, given the constraint of the function sig and the node type, you're limited. You could set up something global, but I really can't recommend that.
Was This Post Helpful? 0
  • +
  • -

#8 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3576
  • View blog
  • Posts: 11,125
  • Joined: 05-May 12

Re: Recursion and Binary Search Trees

Posted 10 August 2012 - 11:11 AM

He! He! He! :cheers:

I tried to be global and threw in the metric thing there for the rest of the world.

Yeah, having a global to switch directions just doesn't feel right.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1