Find the Inorder Predecessor in a Binary Search Tree

Algorithm Steps

If the target node has a left subtree, the inorder predecessor is the rightmost node in that left subtree. Traverse to the left child and then keep moving to the right child until no more right children exist.
If the target node does not have a left subtree, traverse up using the parent pointers until you find an ancestor of which the target node is in the right subtree. That ancestor is the inorder predecessor.
If no such ancestor exists, then the target node has no inorder predecessor.

Find the Inorder Predecessor in a Binary Search Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None, parent=None):
        self.val = val
        self.left = left
        self.right = right
        self.parent = parent

def inorderPredecessor(node):
    if node.left:
        pred = node.left
        while pred.right:
            pred = pred.right
        return pred
    curr = node
    while curr.parent and curr == curr.parent.left:
        curr = curr.parent
    return curr.parent

# Example usage:
if __name__ == '__main__':
    # Construct BST:
    #         20
    #        /  \
    #      10    30
    #        
    #         15
    root = TreeNode(20)
    root.left = TreeNode(10, parent=root)
    root.right = TreeNode(30, parent=root)
    root.left.right = TreeNode(15, parent=root.left)
    node = root.left.right
    pred = inorderPredecessor(node)
    if pred:
        print(f'Inorder predecessor of {node.val} is {pred.val}')
    else:
        print('No inorder predecessor found')