Re: [algogeeks] Re: BST in BT
Maximum Sized Binary Search Tree in a Binary Tree: http://www.rawkam.com/?p=822 On Mon, Sep 27, 2010 at 10:34 AM, Chonku wrote: > @Prodigy > As per your example, 8 15 20 25 which is the is indeed the maximum binary > search tree in this binary tree is only a solution to smaller problem used > to solve a bigger problem. > The solution to smaller problem can be translated directly to the solution > of the bigger problem. > > On Mon, Sep 27, 2010 at 8:28 AM, prodigy <1abhishekshu...@gmail.com>wrote: > >> 15 >> /\ >> 8 25 >> /\ >> 20 22 >> >> >> On Sep 26, 10:45 am, Chonku wrote: >> > This can also be done if we do an inorder traversal of the binary tree >> and >> > look for the longest continuous sequence of numbers in ascending order. >> >> Your idea will fail for above case. >> >> In Order => 8 15 20 25 22 >> longest continuous sequence of numbers in ascending order => 8 15 20 >> 25 >> >> But that's not the answer (I hope you realize what correct output >> would be ) >> >> >> >> >> >> -- >> You received this message because you are subscribed to the Google >> Groups "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST in BT
@Prodigy As per your example, 8 15 20 25 which is the is indeed the maximum binary search tree in this binary tree is only a solution to smaller problem used to solve a bigger problem. The solution to smaller problem can be translated directly to the solution of the bigger problem. On Mon, Sep 27, 2010 at 8:28 AM, prodigy <1abhishekshu...@gmail.com> wrote: > 15 > /\ > 8 25 > /\ > 20 22 > > > On Sep 26, 10:45 am, Chonku wrote: > > This can also be done if we do an inorder traversal of the binary tree > and > > look for the longest continuous sequence of numbers in ascending order. > > Your idea will fail for above case. > > In Order => 8 15 20 25 22 > longest continuous sequence of numbers in ascending order => 8 15 20 > 25 > > But that's not the answer (I hope you realize what correct output > would be ) > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST in BT
For solution to this problem see
http://groups.google.co.in/group/algogeeks/browse_thread/thread/adc95dcf96020a7/2943fd3c5a116fee?hl=en&lnk=gst&q=binary+tree+to+binary+serach+tree#
In that thread, I have a doubt regarding solution posted by @"Algoose
Chase". The code posted is good as I feel except for the condition
if( NodeL->Data > root->data)
{
}
if( NodeR->Data <= root->data)
{
}
Here If you find that the present node's (say 'n1') value if less than
the MAX (say 'n2' ) of so far constructed BST in the left tree, then
if is for sure that that MAX ('n2') of the left tree will replace the
present node 'n1'. This will make sure that all nodes to the left are
less than the new root 'n2', but we are not sure that the remaining
nodes n the left tree are all less than 'n1'.
So in "if( NodeL->Data > root->data)" condition, "temp = root-data;
root->data = NodeL->data" is correct but instead of doing
Nodel->data = root->data;
BinarytoBST(NodeL)
we should simply say
deleteNode(tree->left,NodeL);//This will delete NodeL from a BST
rooted at tree->left, taking into account delete conditions for
deleting right most child of BST //(because NodeL was the
right most child)
InsertNode(tree->left,temp);
Do share your views.
Thanks,
Sourav
On Sep 27, 7:58 am, prodigy <1abhishekshu...@gmail.com> wrote:
> 15
> / \
> 8 25
> / \
> 20 22
>
> On Sep 26, 10:45 am, Chonku wrote:
>
> > This can also be done if we do an inorder traversal of the binary tree and
> > look for the longest continuous sequence of numbers in ascending order.
>
> Your idea will fail for above case.
>
> In Order => 8 15 20 25 22
> longest continuous sequence of numbers in ascending order => 8 15 20
> 25
>
> But that's not the answer (I hope you realize what correct output
> would be )
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST in BT
15 /\ 8 25 /\ 20 22 On Sep 26, 10:45 am, Chonku wrote: > This can also be done if we do an inorder traversal of the binary tree and > look for the longest continuous sequence of numbers in ascending order. Your idea will fail for above case. In Order => 8 15 20 25 22 longest continuous sequence of numbers in ascending order => 8 15 20 25 But that's not the answer (I hope you realize what correct output would be ) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST in BT
This can also be done if we do an inorder traversal of the binary tree and look for the longest continuous sequence of numbers in ascending order. On Sun, Sep 26, 2010 at 11:10 AM, mac adobe wrote: > No parody .. that would be another doubt :( > > > On Sat, Sep 25, 2010 at 11:03 PM, prodigy <1abhishekshu...@gmail.com>wrote: > >> By maintaining a current maximum and a global maximum. You do know how >> to verify a BT is BST . >> >> http://pastebin.com/xwXXTEnP >> >> On Sep 25, 9:04 pm, mac adobe wrote: >> > How would you identify a binary search tree of maximum nodes in a binary >> > tree ? >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST in BT
BSTP : Root's right and left subtrees are BST and value at Root is (greater than largest of left) and (smaller than lowest of right). if BSTP is true, size of this BST is sum of (size of left subtree) and (size of right subtree) plus 1. Compare this value with global maximum. Do it recursively. See the code here http://pastebin.com/xwXXTEnP -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST in BT
@parody :..and how would that find me a maximum size BST .. ?? ( for checking if this BT is BST i would do inorder traversal and see if it is increasing ) On Sun, Sep 26, 2010 at 11:10 AM, mac adobe wrote: > No parody .. that would be another doubt :( > > > On Sat, Sep 25, 2010 at 11:03 PM, prodigy <1abhishekshu...@gmail.com>wrote: > >> By maintaining a current maximum and a global maximum. You do know how >> to verify a BT is BST . >> >> http://pastebin.com/xwXXTEnP >> >> On Sep 25, 9:04 pm, mac adobe wrote: >> > How would you identify a binary search tree of maximum nodes in a binary >> > tree ? >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST in BT
No parody .. that would be another doubt :( On Sat, Sep 25, 2010 at 11:03 PM, prodigy <1abhishekshu...@gmail.com> wrote: > By maintaining a current maximum and a global maximum. You do know how > to verify a BT is BST . > > http://pastebin.com/xwXXTEnP > > On Sep 25, 9:04 pm, mac adobe wrote: > > How would you identify a binary search tree of maximum nodes in a binary > > tree ? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST in BT
By maintaining a current maximum and a global maximum. You do know how to verify a BT is BST . http://pastebin.com/xwXXTEnP On Sep 25, 9:04 pm, mac adobe wrote: > How would you identify a binary search tree of maximum nodes in a binary > tree ? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
