1 Reply Latest reply: May 3, 2008 3:11 PM by 800282 RSS

    Find the largest complete subtree in a Binary Search Tree

    807591
      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.