• Post Reply Bookmark Topic Watch Topic
  • New Topic

How does this binary tree code work?  RSS feed

 
Adam Chalkley
Ranch Hand
Posts: 518
4
  • Mark post as helpful
  • send pies
  • 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








 
Campbell Ritchie
Marshal
Posts: 56533
172
  • Mark post as helpful
  • send pies
  • 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.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • 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
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • 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
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!