Inorder successor

#1

question -->
https://practice.geeksforgeeks.org/problems/inorder-successor-in-bst/1#
code–>


not passing all test cases,it is showing segmentation fault!!!

#2

Hi @sheikhhaji18, your logic is not correct

  1. you are already given the node address of x, but you are finding x->val in tree which will again give you x ,which makes your search function useless
  2. you are assuming that inorder successor always exists in the left subtree of a node, but that is not always the case.
    consider the input for BST as :-
    4 3 2 1 5 6 -1
    and if x= 5
    according to your algorithm you will get -1 but the actual answer is 4

So , what you can do …
actually this is a simple question, u know there is a very special property of BST that inorder of a BST is always sorted .
So just find the largest value in the tree smaller than x->val

In case of any doubt feel free to ask :slight_smile:
Mark your doubt as RESOLVED if you got the answer

#3

okay i made it so complex,and wrong

#4

don’t worry… that’s how you will learn

#5

but in deletion of node in bst we do like that only like–>(when there are two children of the parent node)
for successor
1.go to right,
2.go to left subtree till it hits NULL
but this only works for root node(parent node) right?

#7

yeah , for that our aim is to find the minimum value node in the right subtree , and since in BST we know value at left is smaller than the root we know that in the current tree we can find minimum node by going left

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.