Recursive successor function for a binary search tree (Python)

Question

I'm trying to write a function that will find the smallest value in a binary search tree that is greater than some given x (i.e, the successor of x in the BST). The BST class I'm using is the following:

class BSTree:
 class Node:
 def __init__(self, val, left=None, right=None):
 self.val = val
 self.left = left
 self.right = right
 
 def __init__(self):
 self.size = 0
 self.root = None
 def add(self, val):
 assert(val not in self)
 def add_rec(node):
 if not node:
 return BSTree.Node(val)
 elif val < node.val:
 return BSTree.Node(node.val, left=add_rec(node.left), right=node.right)
 else:
 return BSTree.Node(node.val, left=node.left, right=add_rec(node.right))
 self.root = add_rec(self.root)
 self.size += 1
 def height(self):
 """Returns the height of the longest branch of the tree."""
 def height_rec(t):
 if not t:
 return 0
 else:
 return max(1+height_rec(t.left), 1+height_rec(t.right))
 return height_rec(self.root)
 
 def pprint(self, width=64):
 """Attempts to pretty-print this tree's contents."""
 height = self.height()
 nodes = [(self.root, 0)]
 prev_level = 0
 repr_str = ''
 while nodes:
 n,level = nodes.pop(0)
 if prev_level != level:
 prev_level = level
 repr_str += '\n'
 if not n:
 if level < height-1:
 nodes.extend([(None, level+1), (None, level+1)])
 repr_str += '{val:^{width}}'.format(val='-', width=width//2**level)
 elif n:
 if n.left or level < height-1:
 nodes.append((n.left, level+1))
 if n.right or level < height-1:
 nodes.append((n.right, level+1))
 repr_str += '{val:^{width}}'.format(val=n.val, width=width//2**level)
 print(repr_str)

I'm trying to write a recursive implementation for my own understanding of recursion, but I'm having some trouble. Here's what I have so far:

def successor(self, x):
 
 def successor_rec(node): 
 if node is None: 
 return None
 if x < node.val:
 if node.left is not None and node.left.val > x: 
 return successor_rec(node.left)
 else: 
 return node.val
 else: 
 return successor_rec(node.right)
 
 return successor_rec(self.root)

Consider the following BST:

t = BSTree()
 for x in [6, 3, 5, 4, 7, 1, 2, 9, 8, 0]:
 t.add(x)
 t.pprint()
 6 
 3 7 
 1 5 - 9 
 0 2 4 - - - 8 - 

When I do t.successor(4) I get 6, though I wanted to get 5, the successor of 4 in the tree. I know the problem occurs in the part of the function else: return node.val, though I am struggling to remedy this.

• mkrieger1: What did you expect to get instead?
• Alex: I was expecting to get 5, the smallest value greater than 4 in the tree
• Carcigenicate: On the very first call, node.left.val > x will be false, so execution will jump to return node.val, and 6 is returned.

Answer 1

Your if x < node.val block is not right. For instance, even when node.left.val < x, you should still go find the successor of node.left as it could have a right subtree (node.left.right).

Here is a correction:

 if x < node.val:
 attempt = successor_rec(node.left)
 return node.val if attempt is None else attempt

• Alex: Great, thanks a ton! Your explanation cleared it up for me as well as the correction.