Write a program to determine if a binary tree is well ordered

View previous topic View next topic Go down

Write a program to determine if a binary tree is well ordered

Post  Admin on Wed Aug 24, 2011 2:27 pm

public static boolean judge(TreeNode root){
if(root==null)
return false;
if(root.left){
if(root.left.value>=root.value)
return false;
judge(root.left);
}
if(root.right){
if(root.right.value<=root.value)
return false;
judge(root.right);
}
return true;
}


Code from CareerCup:

boolean verifyBST(Node* aNode)
{
if((aNode->left) && (aNode->left->value > aNode->value))
return false;
if((aNode->right) && (aNode->right->value < aNode->value))
return false;


if(!(aNode->left&&aNode->right)) return true;
else {
if(verifyBST(aNode->left) && verifyBST(aNode->right))
return true;
else
return false;
}
}

Admin
Admin

Posts : 131
Join date : 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

Re: Write a program to determine if a binary tree is well ordered

Post  viterbi on Thu Sep 08, 2011 10:35 pm

I assume by CareerCup, you mean the website, not the book, right?

Anyway, both solutions are very wrong. Actually, in my third round Amazon phone interview, I made the same mistake and was rejected. Shocked Sad Sad

Please think for a moment why it is wrong.

viterbi

Posts : 32
Join date : 2011-09-03

View user profile

Back to top Go down

Re: Write a program to determine if a binary tree is well ordered

Post  Admin on Fri Sep 09, 2011 12:34 am

I have checked the second code and did not consider the aNode is NULL case
Here is the revised version:

boolean verifyBST(Node* aNode){
if(aNode==null)
return true;
if((aNode->left) && (aNode->left->value > aNode->value))
return false;
if((aNode->right) && (aNode->right->value < aNode->value))
return false;


if(!(aNode->left&&aNode->right)) return true;
else {
if(verifyBST(aNode->left) && verifyBST(aNode->right))
return true;
else
return false;
}
}

Admin
Admin

Posts : 131
Join date : 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

Re: Write a program to determine if a binary tree is well ordered

Post  Admin on Fri Sep 09, 2011 12:38 am

Revise for the first code:


public static boolean judge(TreeNode root){
if(root==null)
return true;
if(root.left){
if(root.left.value>=root.value)
return false;
}

if(root.right){
if(root.right.value<=root.value)
return false;
}

if(judge(root.left)&&judge(root.right))
return true;
else
return false;
}

Check me if I'm wrong study

Admin
Admin

Posts : 131
Join date : 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

Re: Write a program to determine if a binary tree is well ordered

Post  viterbi on Fri Sep 09, 2011 9:20 am

No, the error is not some corner cases. There are more fundamental problems there. Think about the definition of BST.

viterbi

Posts : 32
Join date : 2011-09-03

View user profile

Back to top Go down

Re: Write a program to determine if a binary tree is well ordered

Post  Admin on Fri Sep 09, 2011 11:54 am

Is that all the node in left tree are smaller than the root node, and all the node in right tree are bigger than the root node?


viterbi wrote:No, the error is not some corner cases. There are more fundamental problems there. Think about the definition of BST.

Admin
Admin

Posts : 131
Join date : 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

Re: Write a program to determine if a binary tree is well ordered

Post  viterbi on Sun Sep 11, 2011 10:40 pm

OK. I will give more hint. Think: is this a BST?

15
|\
10 18
|\
8 17

What will the answer of your program?

Admin wrote:Is that all the node in left tree are smaller than the root node, and all the node in right tree are bigger than the root node?


viterbi wrote:No, the error is not some corner cases. There are more fundamental problems there. Think about the definition of BST.

viterbi

Posts : 32
Join date : 2011-09-03

View user profile

Back to top Go down

Re: Write a program to determine if a binary tree is well ordered

Post  Admin on Mon Sep 12, 2011 1:45 pm

Yes, that is what I mean, the left tree has node greater than the root, so it is not BST

viterbi wrote:OK. I will give more hint. Think: is this a BST?

15
|\
10 18
|\
8 17

What will the answer of your program?

Admin wrote:Is that all the node in left tree are smaller than the root node, and all the node in right tree are bigger than the root node?


viterbi wrote:No, the error is not some corner cases. There are more fundamental problems there. Think about the definition of BST.

Admin
Admin

Posts : 131
Join date : 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

Re: Write a program to determine if a binary tree is well ordered

Post  viterbi on Tue Sep 13, 2011 9:54 am

But your program will return true.

Admin wrote:Yes, that is what I mean, the left tree has node greater than the root, so it is not BST

viterbi wrote:OK. I will give more hint. Think: is this a BST?

15
|\
10 18
|\
8 17

What will the answer of your program?

Admin wrote:Is that all the node in left tree are smaller than the root node, and all the node in right tree are bigger than the root node?


viterbi wrote:No, the error is not some corner cases. There are more fundamental problems there. Think about the definition of BST.

viterbi

Posts : 32
Join date : 2011-09-03

View user profile

Back to top Go down

Re: Write a program to determine if a binary tree is well ordered

Post  Admin on Tue Sep 13, 2011 1:54 pm

We can implement a in-order-traversal to list all elements in an array and to judge whether the array is in ascending order.

Time complexity O(n)
Space complexity O(n)

Check me if I'm wrong


viterbi wrote:But your program will return true.

Admin wrote:Yes, that is what I mean, the left tree has node greater than the root, so it is not BST

viterbi wrote:OK. I will give more hint. Think: is this a BST?

15
|\
10 18
|\
8 17

What will the answer of your program?

Admin wrote:Is that all the node in left tree are smaller than the root node, and all the node in right tree are bigger than the root node?


viterbi wrote:No, the error is not some corner cases. There are more fundamental problems there. Think about the definition of BST.

Admin
Admin

Posts : 131
Join date : 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

Re: Write a program to determine if a binary tree is well ordered

Post  viterbi on Thu Sep 15, 2011 11:31 pm

This is correct, but it need an additional array, right?

Admin wrote:We can implement a in-order-traversal to list all elements in an array and to judge whether the array is in ascending order.

Time complexity O(n)
Space complexity O(n)

Check me if I'm wrong


viterbi wrote:But your program will return true.

Admin wrote:Yes, that is what I mean, the left tree has node greater than the root, so it is not BST

viterbi wrote:OK. I will give more hint. Think: is this a BST?

15
|\
10 18
|\
8 17

What will the answer of your program?

Admin wrote:Is that all the node in left tree are smaller than the root node, and all the node in right tree are bigger than the root node?


viterbi wrote:No, the error is not some corner cases. There are more fundamental problems there. Think about the definition of BST.

viterbi

Posts : 32
Join date : 2011-09-03

View user profile

Back to top Go down

Re: Write a program to determine if a binary tree is well ordered

Post  Sponsored content


Sponsored content


Back to top Go down

View previous topic View next topic Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum