## Sunday, June 30, 2013

### Binary search tree deletion

A Binary Search tree is generated by inserting in order the following integers: 50, 12, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. Show the result binary search tree after the elements have been deleted in the order 20, 12, 37, 5, 62, 50, 8.

Three possible cases occur when we delete an element of a Binary Search Tree. Deletion of an element should preserve the BST property.

Let the node to be deleted be x.

Case  1: x has no children.
Delete x by making parent of x point to NULL. Parent of x can be obtained through a trailing pointer.

Case 2: x has one child.
Delete x by making parent of x point to x's child, then delete x.

The case 1 and case 2 are simpler compared to the third case, case 3 is a bit trickier.

Case 3: x has two children.
To preserve the binary search tree property we need to copy the immediate successor of x to x's place. The immediate successor of x can be found in right subtree of x. The immediate successor is also the minimum element in the right subtree of x.  Let the immediate successor be y. First we need to search this minimum element y. After we have copied y to x's place, we will have a binary search tree (and the BST property preserved) with duplicates.  y element is at two places and we need to delete the y in the original place. Deleting the y in original place will be either case 1 or case 2.  Deleting y in the original place cannot be case 3 because it is the minimum element in a binary search tree subtree, the minimum element has always one child or no child.

Searching the minimum element in right subtree involves traversing the left pointers from the root node of the subtree. The last non NULL node gives the minimum element in the right subtree of x.

Briefly, copy the minimum element y in the right subtree of x to x's place. Delete the y in original place through case 1 or case 2.

The Binary Search tree is generated by inserting in order the following integers: 50, 12, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. Now let us delete the elements in the order 20, 12, 37, 5, 62, 50, 8.

Share your thoughts in the comments below, to make me describe the blog post  even better and do recommend the post if you found the content helpful!!!

1. All you need to start dealing 58 second binary possibilities will be to find the tool you can deal, start the binary choice sign software package, after that get on the agent therefore you are ready to go. You will select from telephone as well as set possibilities which reach its expiration date in a very small, allowing you to more potent (or poorer) very quickly.

1. Great Article. Thank you for sharing! Really an awesome post for every one.

IEEE Final Year projects Project Centers in Chennai are consistently sought after. Final Year Students Projects take a shot at them to improve their aptitudes, while specialists like the enjoyment in interfering with innovation. For experts, it's an alternate ball game through and through. Smaller than expected IEEE Final Year project centers ground for all fragments of CSE & IT engineers hoping to assemble. Final Year Project Domains for IT It gives you tips and rules that is progressively critical to consider while choosing any final year project point.

JavaScript Training in Chennai

JavaScript Training in Chennai

2. Very useful information on Data Structures, definitely it helps us to protect our site from copied content, if you are Looking for software courses?

Qtp training in Chennai
iOS Training in Chennai
JAVA Training in Chennai
Big Data Training in Chennai
Selenium Training in Chennai
German Classes in chennai

3. Do it yourselfers often take over three months to get their engines installed. I have devised a system outlined below where we can change a main engine in just one week.OMC repair parts

4. This comment has been removed by the author.

5. When making a bonsai, practically any woody stemmed tree or bush can be utilized. Initially you should choose whether you need your bonsai tree inside or outside. Washington state

6. Thanks for sharing the blog it is very helpful
C++ Course in Delhi
C++ Course in Noida
C++ Course in Gurgaon

7. When you initially find out about an Enterprise Artificial Intelligence Sales master the primary idea that rings a bell is that you would likely need to enlist a genuine person that can impart his insight to your group.ai courses

8. Thanks for Sharing a good and helpful blogs for us
3d max training in delhi
3d max training in noida
3d max training in gurugram

9. Informative post indeed, I’ve being in and out reading posts regularly and I see alot of engaging people sharing things and majority of the shared information is very valuable and so, here’s my fine read.

10. thanks for this informative post.
3D max course in noida
3D max course in delhi

11. your blog was really interesting,I have learnt so much.
corporate training course in Delhi
corporate training course in Noida

12. Very informative article, Which you have shared here about the data structure binary search tree. After reading your article I got very much information and it is very useful for us. Thank you for sharing this article here. Video Tutorial to Learn Data Structures

13. The Post was up to the point and described the in order very efficiently. Thanks to blog author for magnificent and educational post.
sas training institute in delhi
sas training institute in noida

3d max training in noida
3d max training in delhi

15. I examine your blog site presently share great information right below. Azure Devops Certification

16. Otherwise, it is compatible with various plug-ins such as Cinema 4D, Autodesk Revit, 3DS Max and Google Sketch-up among others. formation 3ds max Pre-loaded final textures like hair, fur, and grass cut rendering time by almost 50% making total rendering time even faster.

17. very nice blogs!!! i have to learning for lot of information for this sites...Sharing for wonderful information.Thanks for sharing this valuable information to our vision. You have posted a trust worthy blog keep sharing.

Big Data Hadoop Training In Chennai | Big Data Hadoop Training In anna nagar | Big Data Hadoop Training In omr | Big Data Hadoop Training In porur | Big Data Hadoop Training In tambaram | Big Data Hadoop Training In velachery

18. It also investigates data content on social sites or can look into survey responses. The single objective of Big Data analytics is to come to an informed business decision so that company can increase its profit. artificial intelligence certification

19. The article you have shared here is very informative and the points you have mentioned are very helpful. I am really impressed by the way you detailed everything. It’s very informative and you are obviously very knowledgeable in this field. Thank you so much. NATA Coaching.

20. Thanks for the post. It was very interesting and meaningful. I really appreciate it! Keep updating stuff like this. Otherwise anyone can learn 3D Max course so contact here- +91-9311002620 or visit website- https://www.htsindia.com/Courses/cad-cam-cae/autocad-3ds-max-training-course

21. I am glad to post a worthy article about the German Language Course and IELTS Coaching from KCR consultants, this may change your career growth and language skill.

22. Thank you for sharing this valuable post really appreciable post if anyone look for best Python training institute in Delhi Contact Here-+91-9311002620 Or Visit Website- https://www.htsindia.com/Courses/python/python-training-institute-in-south-delhi

23. Big thanks for sharing this post apart form that if anyone look for Python training institute in Delhi Contact Here-+91-9311002620 Or Visit Website- https://www.htsindia.com/Courses/python/python-training-institute-in-delhi

24. Thanks for sharing this amazing post this is the content i really looking for, its very helpful i hope you will continue your blogging anyway if anyone looking for python training institute in delhi contact us +91-9311002620 visit-https://www.htsindia.com/Courses/python/python-training-institute-in-delhi

25. Thanks for sharing this valuable post its very informative and very helpful apart from that if anyone looking for e accounting institute in delhi so Contact Here-+91-9311002620 Or Visit Website- https://www.htsindia.com/Courses/Tally/e-accounting-training-course

26. Thanks for posting these kinds of post its very helpful and very good content a really appreciable post apart from that if anyone looking for C++ training institute in delhi so contact here +91-9311002620 visit https://www.htsindia.com/Courses/modular-courses/c-plus-plus-training-course

27. Thanks for posting these kinds of post its very helpful and very good content a really appreciable post apart from that if anyone looking for C++ training institute in delhi so contact here +91-9311002620 visit

28. Thanks for sharing this amazing post this is the content i really looking for, it's very helpful i hope you will continue your blogging anyway if anyone looking for e accounting training institute in delhi contact us +91-9311002620 visit-https://www.htsindia.com/Courses/Tally/e-accounting-training-course

29. It's a really helpful blog. I really appreciate your information which you shared with us. If anyone wants to create his/her career in MIS. Get a free demo , call on 9311002620 or visit website-https://www.htsindia.com/Courses/business-analytics/mis-training-instiute-in-delhi

31. Thank you so much for this amazing blog. Keep sharing this type of content with us. If anyone wants to learn C++ in Delhi, I will recommend High Technologies Solutions training institute.
For any further information please call +919311002620 or you can visit website https://htsindia.com/Courses/modular-courses/c-plus-plus-training-course

32. Thank you so much for this amazing blog. Keep sharing this type of content with us. If anyone wants to learn TALLY in Delhi, I will recommend High Technologies Solutions training institute.
For any further information please call +919311002620 or you can visit website https://www.htsindia.com/Courses/tally/tally-training-course

33. Thank you so much for this amazing blog. Keep sharing this type of content with us. If anyone wants to learn MIS in Delhi, I will recommend High Technologies Solutions training institute.
For any further information please call +919311002620 or you can visit website https://www.htsindia.com/Courses/business-analytics/mis-training-instiute-in-delhi

34. Thank you for sharing an amazing & wonderful blog. This content is very useful, informative and valuable in order to enhance knowledge. Keep sharing this type of content with us & keep updating us with new blogs. Apart from this, if anyone who wants to join the Python Training institute in Delhi, can contact 9311002620 or visit our website-
https://htsindia.com/Courses/python/python-training-institute-in-south-delhi

35. Developers nowadays have to build a proper understanding of data analysis tools to get a job in an organization.
data science training in bhubaneswar