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.