Win a copy of TensorFlow 2.0 in Action this week in the Artificial Intelligence and Machine Learning forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Paul Clapham
  • Bear Bibeault
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Jj Roberts
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • salvin francis
  • Scott Selikoff
  • fred rosenberger

Node count in a Binary Tree

 
Greenhorn
Posts: 7
Eclipse IDE Oracle Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,
This is my first post on this forum so let's see how it works.
I am trying to get a node count from a Binary Tree but it is only returning 1 instead of 6.
Some background: The tree is constructed from a string with parenthesis. It works just fine for the other methods but my nodeCount() and recNodeCount() are not working.

Here is my constructor


Here are my methods


I will appreciate the help.
Thank you
 
Marshal
Posts: 25961
70
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Pat, welcome to the Ranch!

Your methods to compute the node count look fine to me. But I don't see the code which is calling them, so that makes me suspect either that you're calling the nodeCount() method on a node which isn't the root, or alternatively that the tree-building method isn't working correctly.

But no... your nodeCount() method uses this.root... although your tree-building both sets this.root and returns it to some unknown code which I therefore suspect. And also your tree-building code uses both "this.root" and "root". Those must be the same thing, I suppose, but it's a bit confusing.
 
Saloon Keeper
Posts: 7393
66
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would take the time to write a method that would print out an indented diagram of the tree, or perhaps reconstructing a parenthesized string from a tree. Then inject that print into your code so that you can watch the progression of the tree being built. That would tell you a lot.
 
Paul Clapham
Marshal
Posts: 25961
70
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If I ignore the code and just use the fact that nodeCount() returns 1, it follows that the node used by nodeCount() has null for both its left and right nodes.

Now when I look at the code, I see that setting root.leftNode and setting root.rightNode are inside if-statements so they might not be executed. I agree with Carey's suggestion to write code which tests your tree-building, but to start with you could simply put in debugging statements to see if root.leftNode and root.rightNode are assigned values or not.
 
Carey Brown
Saloon Keeper
Posts: 7393
66
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm still thinking this through, but it seems that you shouldn't be using 'root' when you are inside a recursive method. That you should be passing the current node you are working on down through the recursion.
 
Carey Brown
Saloon Keeper
Posts: 7393
66
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For example
Translates into
 
Pat Watson
Greenhorn
Posts: 7
Eclipse IDE Oracle Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Paul Clapham wrote:If I ignore the code and just use the fact that nodeCount() returns 1, it follows that the node used by nodeCount() has null for both its left and right nodes.

Now when I look at the code, I see that setting root.leftNode and setting root.rightNode are inside if-statements so they might not be executed. I agree with Carey's suggestion to write code which tests your tree-building, but to start with you could simply put in debugging statements to see if root.leftNode and root.rightNode are assigned values or not.



Hi Guys,
I am trying to understand this a little better. So, I pass this tree to the method/Constructor
BinaryTree tree = new BinaryTree("(A(G(J)(1))(Z(5)))");

and here is where I call the nodeCount: System.out.println(tree.nodeCount());
When I call other methods such as toString() or height(), I get the correct outputs but the nodeCount is the problem right now. I have attached the entire file for your review.
Also, can I get additional input on Cary's step by step code? or an example if you don't mind?
Thank you again for all the help

 
Carey Brown
Saloon Keeper
Posts: 7393
66
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Carey Brown wrote:I'm still thinking this through, but it seems that you shouldn't be using 'root' when you are inside a recursive method. That you should be passing the current node you are working on down through the recursion.


Or rather, using a local variable 'current' as opposed to 'root' and then returning 'current'. This would mean  that the constructor would need to assign the returned value to root.

Nit pick: It is a Java convention that all methods begin with a lower case letter. BTree() does not follow that convention and is confusing. It is also confusing to have both 'root' and 'this.root' in the same method, implying that there are two separate variables when, in fact, they are the same.
 
Carey Brown
Saloon Keeper
Posts: 7393
66
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nit pick: I tend to think of a "root node" as the root of the entire tree, not the root of a branch. Why not just call it "node"?
 
Pat Watson
Greenhorn
Posts: 7
Eclipse IDE Oracle Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Carey Brown wrote:Nit pick: I tend to think of a "root node" as the root of the entire tree, not the root of a branch. Why not just call it "node"?



Thank you Casey. I took those advices. Can you give me a little more information by what you meant with creating a test code to create the tree? The one I have right now seems to work for other methods I have but not this one and I don't know how I deconstruct it piece by piece even though I know it would help.
 
Pat Watson
Greenhorn
Posts: 7
Eclipse IDE Oracle Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Carey Brown wrote:Line 53: you need to leave off "root."


Taking it off gives me an error message (I would have to change the nodeInfo, etc. to static).
 
Carey Brown
Saloon Keeper
Posts: 7393
66
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Even though you've written this as a recursive method it never get to call itself, therefore, the entire string is treated as one node.
 
Carey Brown
Saloon Keeper
Posts: 7393
66
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your BTNode toString( BTNode ) method is  accurate, but hides misinterpretation of the parens during parsing. In this method, replace the parens with "<" and ">" and you get:
NOW you can see the problem
 
Carey Brown
Saloon Keeper
Posts: 7393
66
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would seriously consider refactoring your BTNode(String) method.
  • Break it into two methods with one doing nothing but matching closing parens.
  • Use a 'current' local variable instead of 'root'.

  • Here's an example of the helper method.
    You can use the return value as a parameter to a substring() call.
    reply
      Bookmark Topic Watch Topic
    • New Topic