• Post Reply Bookmark Topic Watch Topic
  • New Topic

Issue with deep copy of binary search tree  RSS feed

 
Gabrielle Evans
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
First of all, I understand that there are many similar questions to mine posted around the web. I have spent, literally, 2 hours looking through and attempting some of the solutions already given. I am at my wits end. I have a BST that I am told (this is for homework) that I must do a deep copy of into a separate tree. I am told to to this my implementing a preorder traversal method. This is what I have so far



I am doing it in 2 seperate methods because the specifications require a method BSTNode copy() that calls a preorder traversal method.

Here is my BSTNode class for reference



When I attempt to run the code, I get that only the first element (root) of the tree gets copied. Here is the code I am using to test



My output is

I really am desperate. This is about the 8th time I have completely re-written my copy method(s). Any guidance would be greatly appreciated.
 
Maxim Karvonen
Ranch Hand
Posts: 121
12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, Gabrielle.

The problem in the code is that you does not attach new children nodes to a it's parent node. You traverse a tree, you make copies for nodes but just does not link new nodes to each other.

I think you have a widespread misconception about how method arguments work.

Lets start with a very simple example. Try to predict an output of the following code. Then run that code and check an actual result.


If you guesses are wrong then you should learn more about variables. Read a cup story (both parts) and Java is always pass by value. Yes, it's all about passing. You always pass some value. Value of a variable, value of some expression, null value. These all are values. You can't pass a "variable" itself, you can't pass a "reference to a variable", you can only pass a value of that variable. And that value will be assigned to a new variable inside a method. Changing a variable inside method will not change original variable (they are different variables).

And now back to your code. You never set left/right branches of you tree in a copying code. If you think, that you are doing it in lines 17-18 in you first code fragment then you are mistaken. You cannot change value of the copiedTreeRoot.getLetf() inside a recursive call. You should use return value of a copyTree somehow. You have all required methods and just need to figure out which one to call.
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!