Inorder successor for a BST node: Attribute Error for some nodes

Question

I am trying to solve GeeksforGeeks problem Inorder Successor in BST:

Given a BST, and a reference to a Node x in the BST. Find the Inorder Successor of the given node in the BST.

Solutions are discussed at GeeskforGeeks, and I looked at the second approach listed there:

Method 2 (Search from root)

Parent pointer is NOT needed in this algorithm. The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.

I took this approach, but don't understand why my attempt doesn't work as expected. This is what I tried:

def inorder_successor(root, x):
  if x.right != None :
      t = x.right 
      while t.left != None:
        t = t.left
        #print(t.elem)
      return t  
  if root.left == None or root.right:
    return
  if root.left == x:
    return root 

  inorder_successor(root.left, x)
  inorder_successor(root.right, x)
  
def inorder(root):
  if root == None:
    return

  inorder(root.left)
  print(root.elem, end = ' ')
  inorder(root.right)
  
class BTNode:
  def __init__(self, elem):
    self.elem = elem
    self.right = None
    self.left = None

# Create input BST    
n20 = BTNode(20)
n8  = BTNode(8)
n22 = BTNode(22)
n4  = BTNode(4)
n12 = BTNode(12)
n10 = BTNode(10)
n14 = BTNode(14)

n20.left = n8
n20.right = n22

n8.left = n4
n8.right = n12

n12.left = n10
n12.right = n14

print('Given Tree Inorder Traversal: ', end = ' ')
inorder(n20) #Given Tree Inorder Traversal:  4 8 10 12 14 20 22
print()

# This works:
x = n8
print(f'Inorder successor of node {x.elem}: {inorder_successor(n20, x).elem}') #Inorder successor of node 8: 10

# This doesn't work (None). Expected 8
x = n4
print(f'Inorder successor of node {x.elem}: {inorder_successor(n20, x).elem}')  # Error

Here is the tree that the above code tries with:

     20
    /  \
   8    22
  / \
 4   12
    /  \
  10    14

Problem

My code is not giving the right output when calling inorder_successor for nodes like n10 or n4: it produces an error because the inorder_successor function returns None.

However, if I print the n20.elem in line 11 it works and prints the required node element. So I am confused that this is working, but the code gives an error ("'NoneType' object has no attribute 'elem'"). The code works for nodes like n20 though.

Where is my mistake?

Answer 1

The following part of your code has several issues:

  if root.left == None or root.right:
    return
  if root.left == x:
    return root 

  inorder_successor(root.left, x)
  inorder_successor(root.right, x)

• The or root.right part will make the if condition true whenever the root has a right child, which is always the case in the non-recursive call of your function, and so your function returns None in all cases when this part of the code executes (which is when x has no right child).

• The only time this logic returns a node is where you have return root, and in that case x is its left child. But this assumes that if the successor of x is not its descendant, then it must be its immediate parent of which it must be the left child. This is not generally true. The successor of x might be its grand(grand(grand))parent...

• The recursive calls serve no goal, since after having done all the work, your code does not look at what they return

• The fact that this tree is a BST is not exploited in this part of your code. For instance, when x.elem is greater than root.elem, it makes no sense to look in root.left as it is certain that the successor of x can only be at the right side.

Correction

As you already have pointed to a resource that has provided correct code and explanation, I'll just provide here a solution that maintains the idea of using recursion.

The quoted part of your code can be replaced with this:

  if root:
      if x.elem > root.elem:  # must go right:
          return inorder_successor(root.right, x)
      if x.elem < root.elem:  # go left, but root might be the successor
          return inorder_successor(root.left, x) or root