• 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

Deleting node with 2 child nodes in Binary Search Tree

 
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am trying to implement a Delete function in Binary Search Tree. The Delete function works fine when node to be deleted is not root node and has no or one child node. When node to be deleted is not root node and has two child nodes, the program stops working and a window pops up saying "main.exe" file has stopped working" ("main" is the name of the cpp file). If the node to be deleted is root node, the Delete function only works when the root node has no child nodes. When the root node has at-least one child node, the program stops working and a window pops up saying "main.exe" file has stopped working" ("main" is the name of the cpp file) and i can't seem to figure out the problem. Code is given below. I am using code blocks , windows 8.1.
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, there's a lot of code there but nothing which tells us what "doesn't work" means. Please have a look at our FAQ pages ItDoesntWorkIsUseless and TellTheDetails, and post again.
 
yousaf khan
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have edited the post. If you need any other detail, you can ask and i will try to provide it for you. The problem is specifically in the Delete function.
 
Paul Clapham
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
We don't need "any detail". We need a description of your problem. That's not just a detail, it's essential for us to know what is wrong. Look again at the links I provided, they tell you how to describe a problem.
 
yousaf khan
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have edited my question and tried to describe what the problem is.
Please note that English is not my native language so i might not be able to explain the problem as you want me to.
 
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Have you tried debugging your code? You can print tracing information to the console to isolate the lines where the problem occurs.
 
yousaf khan
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The problem is caused because of line 171, 178 and 185.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There's nothing wrong with dereferencing ptr and temp in those calls, so the problem must occur in a deeper stack frame.

At the start of Delete(), print the data of the ptr to see which node causes the problem.
 
yousaf khan
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Actually i have no idea how to use Debugger.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
http://wiki.codeblocks.org/index.php/Debugging_with_Code::Blocks
 
yousaf khan
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
ok so i have used the Debugger although i haven't completely understood yet how to identify the problem using Debugger but anyways i set the break-point at line 160 and i ran the Debugger. I inserted two values in the Tree. First value was 5 and second one was 7. Then i called the delete function to delete 5 from the Tree and as i executed the Delete Function step by step, the call stack window showed the problem to be at line 199. Stack turned RED when line 199 was executed and a small tab appeared on the right bottom corner of the screen saying "program received SIGSEGV signal, segmentation fault". Does this helps you identify the problem ?
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Line 199 is not a statement.

The line numbers in our code viewer are a bit wacky. Can you please copy the piece of code where the segfault happens?
 
yousaf khan
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
it happens at this line ---> if(temp2->left==temp)
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
temp2 contains an illegal memory address, which you're trying to dereference.

That means ReturnParentAddress() is broken.
 
yousaf khan
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes you are right, problem was actually in the ReturnParentAddress function and it is solved now. Thank you Stephan for your help.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Glad you sorted it out

You'll see that debuggers are really useful tools, especially with tree-like data structures.
 
We don't have time to be charming! Quick, read this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic