@priya here is algorithm Algorithm: (With Using Parent Pointer ) 1) If right subtree of node is not NULL, then successor lies in right subtree. Do following. Go to right subtree and return the node with minimum key value in right subtree. 2) If right sbtree of node is NULL, then successor is one of the ancestors. Do following. Travel up using the parent pointer until you see a node which is left child of it’s parent. The parent of such a node is the successor
If We have already given BST (e.g. need not to build then inorder successor can be found in O(N) N number of nodes in tree) but it uses parent pointer overhead :) Can't we do without parent pointer ? We Can Also Do The .without using parent pointer for detail of both code & algorithm you can refer http://shashank7s.blogspot.com/2011/03/wap-to-inorder-successor.html i have given complexity analysis as well !!! Do notify me via mail if anything wrong ? Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/UcXoGH22TrcJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
