Question : Write a function to find inorder successor of a given node in a binary search tree. Our inclination would be to write tree minimum of right subtree. Because we already use this mechanism while deleting a node with both subtrees. But what we fail to notice is that tree minimum of right subtree would be present if there IS a right subtree. What if the node has no right child? What if it is a leaf node? Which nodes are successors of these nodes? And how do we find them? The inorder successor of 3 can be found out as tree minimum of right subtree, which is 4. But what about successors of 4? Or 7? Or successor 13? One method would be to store parent link in each node. And travel up finding parent nodes until the parent node has a value greater than given node. But that needs modification of the structure. Another method is to start from root node and search for a given value and store node with larger value as successor and terminate when we come across a node with
Question: Write a function to delete every k th node from circular linked list until only one node is left. This has a story associated with it. Flavius Josephus was Jewish Historian from 1st century. He and 40 other soldiers were trapped in a cave by Romans. They decided to kill themselves rather than surrendering to Romans. Their method was like this. All the soldiers will stand in a circle and every k th soldier will be shot dead. Josephus said to have calculated the starting point so that he would remain alive. So we have similar problem at hand. We delete every kth node in a circular list. Eventually only one node will be left. e.g. Let us say this is our list And we are deleting every third node. We will delete 30. Then we delete 60. Next we delete 10. Next it will be 50. Next to be deleted is 20. Next 80. This continues. Implementation We can count k-1 nodes and delete next node. This can be repeated in a loop. What must be the terminating condition