For those who is not so clear about inorder successors.


  • 19
    F

    Here is a good explaination I found:
    http://stackoverflow.com/questions/5471731/in-order-successor-in-binary-search-tree

    If you have right child, do this approach (case 1 above):

    enter image description here

    If you don't have a right child, do this approach (case 2 above):

    enter image description here


  • 2
    F

    Python solution of iterative and recursive:

    #method 1: iterative :

    def  inorderSuccessor(self,root,p):
            suc=None
            while root:
           #     if root.val>p.val: #if root.val=p.val we still move right, cause we need find a value greater than him.
                    #greater value is successor candidate:
                    suc=root
                    root=root.left
                else:
                    root=root.right
            return suc
    

    #method 2: recursive:

    def inorderSuccessor(self,root,p):
            if root == None:return None
            if root.val>p.val:#means root is at right side of p, then move left:
                suc=self.inorderSuccessor(root.left,p)
                #suc is none means this is a dead end, and since we are moving left, so successor is the previous one, which is root.
                if suc !=None:
                    return suc
                else:
                    return root
            else:
                #means root is at right side of p, it could be the successor,if it's left value 
                # Or it could be far right from P, then move left:
                return self.inorderSuccessor(root.right,p)

  • 1

    I method 1, p is not used???


  • 0
    S

    http://www.geeksforgeeks.org/?p=9999
    I found this page quite useful. Hope it helps!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.