# 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, ...

1. ## 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. ## 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. ## 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.