BST Operations: Pseudocode (Part 3)

The getSuccessor function

Another property of a binary search tree is that we can easily find the successor of a node. The successor of node A is node B, with the closest bigger value than node A. In other words, B > A and there is no other node C where C > A and C < B.

For example, finding the successor (or predecessor) value is useful to efficiently find the colleague with the closest age (or height, income, and so on) to ours.

Let’s consider the following BST and try to find the successor node for some of the nodes inside the tree.

• The successor of node 1 is node 2 because 2 is the first value bigger than 1.
• The successor of node 2 is node 4 because 4 is the first value bigger than 2. Note that a successor is not the next consecutive value but the first bigger value.
• The successor of node 14 is 15 because 15 is the first value bigger than 14.
• The successor of node 7 is 8 because 8 is the first value bigger than 7.
• Node 16 doesn’t have a successor because it’s the biggest value inside the tree. In other words, the rightmost node in a BST does not have a successor because it’s the biggest node.

Spend time analyzing the tree and ensuring you understand the concept of a successor node.

Let’s try to find an algorithm for determining the successor node.

We’ll look at some of the nodes to try to find an algorithm:

• If we look at node 2, its successor is node 4, which is its right child.
• If we look at node 7, its successor is node 8, which is inside the right subtree of 7, but it is not the immediate right child (which would be 15).
• From these two observations, we can say that the successor of node A is somewhere inside the right subtree of A. But, if we also recall that the right subtree contains only values bigger than the value of A, we can deduce that the successor of node A is the minimum value in the right subtree. It makes sense since the successor is the first bigger value than node A.
  • The minimum value in the right subtree of 2 is 4. Therefore 4 is the successor of 2.
  • The minimum value in the right subtree of 7 is 8. Therefore 8 is the successor of 7.
  • Recall that to find the minimum value in a tree (or subtree), we find the leftmost node in that tree (or subtree). For example, 8 is the leftmost node in the right subtree of 7.

See the following ...