• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

How does this binary tree code work?

 
Ranch Hand
Posts: 545
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi guys something that is really driving me crazy because I understand how it works but at the same time I don't get why it works,ok so lets say I first call the method insert with an empty(null) Node(tree),after the insert method method call newNode now points/refers to that newly created node lets say I repeat this process a few times and to end where I insert the node and the value 7 into the insert method now newNode points/refers to that newly created node,

now I call the search method on my node(tree) I enter my node into the search method and the value of the node I want to find in this case it is 9,so the search method begins

it checks if the node is null which it's not so then it checks if the value is less than the nodes key value which is 7??(because newNode is pointing to the node with the value 7??) this is false so it the returns the search method with the nodes right value which is pointing to null?? and the value  the recursive method runs again before it can find a base case, it then again checks if node == null in this case it does because we passed node.right as a arguement and node.right equals null so it returns null,

but this brings me to the point where I'm confused,how does this code work when I search for the number 9 it returns the node with the value 9,and when I type any other value I called insert on it works fine,when I type in a number I didn't call insert on it gives me a null pointer error,so yeah how come this works because I thought newNode is pointing/referring to the last created object which was 7?

thanks








 
Marshal
Posts: 79405
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Why are you adding Nodes to the tree? I don't think you shou‍ld do that. I think the nodes shou‍ld be private to the tree, so you only add values. The tree object does the adding of nodes. Also, I don't think you would normally return the Node added. You might return true if you have really added a node, but not the node itself.
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Adam Chalkley wrote:ok so lets say I first call the method insert with an empty(null) Node(tree),after the insert method method call newNode now points/refers to that newly created node lets say I repeat this process a few times and to end where I insert the node and the value 7 into the insert method now newNode points/refers to that newly created node,



The second part isn't true. Take a look at your code again. It only returns the newly created node, if the passed in reference is null. If it isn't null, it will do a recursive call to the left or the right... and after it completes the recursive call, it will assign the left or the right, and then, return the original node value (and not the newly created node).

Henry
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Adam Chalkley wrote:
it checks if the node is null which it's not so then it checks if the value is less than the nodes key value which is 7??(because newNode is pointing to the node with the value 7??) this is false so it the returns the search method with the nodes right value which is pointing to null?? and the value  the recursive method runs again before it can find a base case, it then again checks if node == null in this case it does because we passed node.right as a arguement and node.right equals null so it returns null,



First, the top node is not 7, it is 5, as explained in the previous post.  And second (from bold quote), how do you know that the right (or left) is null? Isn't the value of 9 in the tree? And if so, shouldn't it find it?  If that is not what you are seeing, then take a look at the insert() method again -- perhaps, it is not setting the left and right correctly.

Henry
 
I've read about this kind of thing at the checkout counter. That's where I met this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic