Course contentsShow
← Computer Science
Lesson 512 of 2,87212. Binary Search TreesFree lesson

Finding Inorder Predecessor

Locate the inorder predecessor: the rightmost node in the left subtree or the first ancestor from a right turn.

What You'll Learn

You'll learn how to find the inorder predecessor—the node that comes immediately before a given node in sorted order within a Binary Search Tree.

What Is the Inorder Predecessor?

The inorder predecessor of a node is the node that would appear directly before it if you performed an inorder traversal (left-root-right). Since inorder traversal of a BST visits nodes in ascending order, the predecessor is simply the next smaller value.

Two Cases to Consider

Finding the predecessor follows a clear logic based on the tree's structure:

Case 1: Node Has a Left Subtree

If the node has a left child, the predecessor is the rightmost (maximum) node in that left subtree. Think of it like this: you go left once (to get smaller values), then keep going right as far as possible to find the largest of those smaller values.

    50
   /
  30
    \
     40  ← predecessor of 50

Case 2: No Left Subtree

If there's no left child, you must travel up the tree. The predecessor is the first ancestor where you arrived from a right turn—meaning the first ancestor that is smaller than your current node.

    50
      \
       70  ← you're here
      /
    60  ← predecessor (50 is the ancestor from a right turn)

If you never took a right turn going up (always coming from left children), there is no predecessor—you're at the minimum node.

Analogy

Imagine a sorted phone book. Your predecessor is the entry right before yours. If there are entries indented under you to the left, pick the last one in that group. Otherwise, backtrack to find who you're nested under from the right side.

Key Takeaway: The inorder predecessor is either the maximum value in the left subtree, or the nearest ancestor reached via a right-child link.