This discussion is archived
1 Reply Latest reply: May 3, 2008 1:11 PM by 800282 RSS

Find the largest complete subtree in a Binary Search Tree

807591 Newbie
Currently Being Moderated
I'm writing a program for my data structures course that needs to find the largest complete subtree within a binary search tree.
I add integers individually to the STree and an ArrayList that has "-1"s in every void spot of the Stree.

so if the STree looks like this:

50
12 57
6 18 69
16

The ArrayList looks like this:
[50, 12, 57, 6, 18, -1, 69, -1, -1, 16]

I have already been able to successfully create both the STree and the ArrayList.

Now I need to find the largest subtree within the Binary Tree. In this case, it is [50, 12, 57, 6, 18].

However, if the tree looked like this:
50
57
52 69
51 53

The largest subtree would be [57, 52, 69, 51, 53].

I would post what code I have so far, but I don't have any clue how to do this.

If somebody has some clue as to how to do this, please post an example algorithm or something. I'm completely stumped.

Thanks.