How to solve the following binary search tree problem - Java

This is a discussion on How to solve the following binary search tree problem - Java ; My program is to read data from a txt file to Binary Search Tree, then using a method that traverses the tree and prints to standard output the number of nodes which have exactly 2 great grand children. By far, ...

+ Reply to Thread
Results 1 to 3 of 3

How to solve the following binary search tree problem

  1. Default How to solve the following binary search tree problem

    My program is to read data from a txt file to Binary Search Tree, then
    using a method that traverses the tree and prints to standard output
    the number of nodes which have exactly 2 great grand children. By
    far, i can read the data from a txt file but, for the search for
    exactly 2 great grand children, I still get no idea. I want to check
    the tree from root, whenever there is going down to level 2(which is
    the grand children level). I use a counter to count the nodes. then
    if (the counter>=2), check the counters. But this method seems to be
    failed as I want to use recursive function to do. Any one gives me
    idea? Any help would be appreciated. Thanks.

  2. Default Re: How to solve the following binary search tree problem

    SamuelXiao wrote:
    > My program is to read data from a txt file to Binary Search Tree, then
    > using a method that traverses the tree and prints to standard output
    > the number of nodes which have exactly 2 great grand children. By
    > far, i can read the data from a txt file but, for the search for
    > exactly 2 great grand children, I still get no idea. I want to check
    > the tree from root, whenever there is going down to level 2(which is
    > the grand children level). I use a counter to count the nodes. then
    > if (the counter>=2), check the counters. But this method seems to be
    > failed as I want to use recursive function to do. Any one gives me
    > idea? Any help would be appreciated. Thanks.


    Here's an outline for a straightforward but not especially
    efficient approach: Traverse the tree visiting each node in turn,
    and if the node has exactly two great-grandchildren print it.

    This approach decomposes into two sub-problems, the traversal
    and the testing. The traversal is easy to do recursively:

    to traverse a tree or sub-tree rooted at node N:
    if N has exactly two great-grandchildren
    print N
    if N has a left child
    traverse the sub-tree rooted at that child
    if N has a right child
    traverse the sub-tree rooted at that child

    The other task is to count the great-grandchildren of node
    N. Here's one way:

    to count the great-grandchildren of N:
    sum = 0
    if N has a left child
    sum += grandchildren of that child
    if N has a right child
    sum += grandchildren of that child
    now we know N has exactly `sum' great-grandchildren

    How to count the grandchildren? Same outline:

    to count the grandchildren of N:
    sum = 0
    if N has a left child
    sum += children of that child
    if N has a right child
    sum += children of that child
    now we know N has exactly `sum' grandchildren

    Now all you need is to be able to count the direct children of
    a node N, and you're all set. But wait: There's an important
    simplification available. Have you noticed that the way you
    count great-grandchildren is structurally the same as the way
    you count grandchildren? Instead of writing separate methods
    for great-grandchildren, grandchildren, and children, maybe you
    could write just one method to count the children K levels below
    a node N and use it recursively:

    to count the K-children of N:
    sum = 0
    if K > 0
    if N has a left child
    sum += the (K-1)-children of that child
    if N has a right child
    sum += the (K-1)-children of that child
    now we know N has exactly `sum' K-children

    As I said, this approach is not terribly efficient: It visits
    every node once during the traversal, and up to three additional
    times while counting descendants. The task can be done with less
    running around, and I encourage you to try to find other ways.

    --
    Eric.Sosman@sun.com

  3. Default Re: How to solve the following binary search tree problem

    On Nov 6, 12:23 am, Eric Sosman <Eric.Sos...@sun.com> wrote:
    > SamuelXiao wrote:
    > > My program is to read data from a txt file to Binary Search Tree, then
    > > using a method that traverses the tree and prints to standard output
    > > the number of nodes which have exactly 2 great grand children.  By
    > > far, i can read the data from a txt file but, for the search for
    > > exactly 2 great grand children, I still get no idea.  I want to check
    > > the tree from root, whenever there is going down to level 2(which is
    > > the grand children level).  I use a counter to count the nodes.  then
    > > if (the counter>=2), check the counters.  But this method seems to be
    > > failed as I want to use recursive function to do.  Any one gives me
    > > idea?  Any help would be appreciated.  Thanks.

    >
    >      Here's an outline for a straightforward but not especially
    > efficient approach: Traverse the tree visiting each node in turn,
    > and if the node has exactly two great-grandchildren print it.
    >
    >      This approach decomposes into two sub-problems, the traversal
    > and the testing.  The traversal is easy to do recursively:
    >
    >         to traverse a tree or sub-tree rooted at node N:
    >             if N has exactly two great-grandchildren
    >                 print N
    >             if N has a left child
    >                 traverse the sub-tree rooted at that child
    >             if N has a right child
    >                 traverse the sub-tree rooted at that child
    >
    >      The other task is to count the great-grandchildren of node
    > N.  Here's one way:
    >
    >         to count the great-grandchildren of N:
    >             sum = 0
    >             if N has a left child
    >                 sum += grandchildren of that child
    >             if N has a right child
    >                 sum += grandchildren of that child
    >             now we know N has exactly `sum' great-grandchildren
    >
    > How to count the grandchildren?  Same outline:
    >
    >         to count the grandchildren of N:
    >             sum = 0
    >             if N has a left child
    >                 sum += children of that child
    >             if N has a right child
    >                 sum += children of that child
    >             now we know N has exactly `sum' grandchildren
    >
    > Now all you need is to be able to count the direct children of
    > a node N, and you're all set.  But wait: There's an important
    > simplification available.  Have you noticed that the way you
    > count great-grandchildren is structurally the same as the way
    > you count grandchildren?  Instead of writing separate methods
    > for great-grandchildren, grandchildren, and children, maybe you
    > could write just one method to count the children K levels below
    > a node N and use it recursively:
    >
    >         to count the K-children of N:
    >             sum = 0
    >             if K > 0
    >                 if N has a left child
    >                     sum += the (K-1)-children of that child
    >                 if N has a right child
    >                     sum += the (K-1)-children of that child
    >             now we know N has exactly `sum' K-children
    >
    >      As I said, this approach is not terribly efficient: It visits
    > every node once during the traversal, and up to three additional
    > times while counting descendants.  The task can be done with less
    > running around, and I encourage you to try to find other ways.
    >
    > --
    > Eric.Sos...@sun.com


    The problem has been solved, thanks.

+ Reply to Thread