Geeks To Go is a helpful hub, where thousands of volunteer geeks quickly serve friendly answers and support. Check out the forums and get free advice from the experts. Register now to gain access to all of our features, it's FREE and only takes one minute. Once registered and logged in, you will be able to create topics, post replies to existing threads, give reputation to your fellow members, get your own private messenger, post status updates, manage your profile and so much more.

Create Account How it Works

# Pascal Help - Binary Trees

### #1 zell_ffhut Posted 12 November 2005 - 07:02 PM

zell_ffhut

Member

• Member
• 34 posts
Have been trying to write a piece of code, that will allow me to spot weather a tree is a correct Binary Tree, or not.

I feel im quite close to cracking it, but the whole thing is now really confusing me. Can anyone see where im going wrong?

```procedure TraverseTree(var flag: integer;t: BinaryTree);
// Traverse Tree
Begin

If t <> nil then
Begin
with t^ do
TraverseTree(flag, t^.left);
if ((t^.left<> nil) AND (t^.right <> nil)) Then
begin
if t^.left.data > t.data then
flag := flag + 1
else
flag := flag;
end;
TraverseTree(flag, t^.right);
if ((t^.left<> nil) AND (t^.right <> nil)) Then
begin
if t^.right.data < t.data then
flag := flag + 1
else
flag := flag;
end
End

End;

flag: integer;
begin

flag := 0;
ans.known := true;
TraverseTree(flag, t);

If flag = 0 then
Else

IsItABinarySearchTree := ans
End;

```

Any help would be fantastic
• 0

### #2 gust0208 Posted 12 November 2005 - 09:37 PM

gust0208

Member

• Member
• 311 posts
Hello,

I had a few questions about the code and your goal. Are you testing to see if the tree is just a binary tree or a "full" binary tree or "perfect" tree? It looks from the code as if you are testing to see if it is a "full" binary tree since your data structure, BinaryTree, by default makes it a binary tree by only allowing 2 children per node.

What is the "data" variable that you are testing in each node? The values in each node have no bearing on whether it is a binary tree, that is only concerned with the data structure.

It appears from the code (if t^.left.data > t.data then ...) that you want the function to return a "false" value if one of the children values is greater than it's parent. From appearance of the code, it appears as if you are testing to see in the BinaryTree is a valid minimum binary heap?

Let us know your exact goals for testing the tree and we should be able to get it working.

Cheers,
Tom

Have been trying to write a piece of code, that will allow me to spot weather a tree is a correct Binary Tree, or not.

I feel im quite close to cracking it, but the whole thing is now really confusing me. Can anyone see where im going wrong?

```procedure TraverseTree(var flag: integer;t: BinaryTree);
// Traverse Tree
Begin

If t <> nil then
Begin
with t^ do
TraverseTree(flag, t^.left);
if ((t^.left<> nil) AND (t^.right <> nil)) Then
begin
if t^.left.data > t.data then
flag := flag + 1
else
flag := flag;
end;
TraverseTree(flag, t^.right);
if ((t^.left<> nil) AND (t^.right <> nil)) Then
begin
if t^.right.data < t.data then
flag := flag + 1
else
flag := flag;
end
End

End;

flag: integer;
begin

flag := 0;
ans.known := true;
TraverseTree(flag, t);
If flag = 0 then
Else

IsItABinarySearchTree := ans
End;
```

Any help would be fantastic

• 0

### #3 zell_ffhut Posted 13 November 2005 - 06:14 AM

zell_ffhut

Member

• Topic Starter
• Member
• 34 posts
Hi Tom

Im trying to test it to see if it is a correct Binary Tree.

Each node contains an integer. Im trying to test the nodes to make sure the left child is lower, and the right child is higher then the parent node.

Chris.
• 0

### #4 zell_ffhut Posted 13 November 2005 - 06:42 AM

zell_ffhut

Member

• Topic Starter
• Member
• 34 posts
Well, i've just had what i'd like to call "A moment of clairty" And i spoted a few massive flaws, and it now works

Thanks for your comments Tom, i think they help me realise the flaws!
• 0

### #5 gust0208 Posted 13 November 2005 - 10:38 AM

gust0208

Member

• Member
• 311 posts
Hey, no worries and glad it worked out!

Feel free to post any more questions and I can keep myself brushed up on Pascal syntax.

Cheers,
Tom

Well, i've just had what i'd like to call "A moment of clairty" And i spoted a few massive flaws, and it now works

Thanks for your comments Tom, i think they help me realise the flaws!

• 0

### #6 zell_ffhut Posted 13 November 2005 - 01:02 PM

zell_ffhut

Member

• Topic Starter
• Member
• 34 posts
If anyone knows how to find the height of branches in a binary tree, that would be a great help.

Im trying to implement a similar program now, but for AVL trees.
• 0

### #7 gust0208 Posted 13 November 2005 - 07:58 PM

gust0208

Member

• Member
• 311 posts
Hello,

Finding the height would largely depend on how you are representing your binary tree structure (array, linked list, etc.). Basically, you just need a function to traverse the each node's subtree and increment a counter by one. By definition, you will get the height within one even if you just follow one node all the way down to the base (say, always follow the left child node). There is a great wikipedia page on balanced AVL trees, you can check it out here:

http://en.wikipedia.org/wiki/AVL_tree

Let us know what language you are working in and we should be able to help you out.

Cheers,
Tom

If anyone knows how to find the height of branches in a binary tree, that would be a great help.

Im trying to implement a similar program now, but for AVL trees.

• 0

### #8 zell_ffhut Posted 13 November 2005 - 08:01 PM

zell_ffhut

Member

• Topic Starter
• Member
• 34 posts
working on pascal again
• 0

### Similar Topics

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users