Finding the Predecessor and Successor Node of a Binary Search Tree

A Binary Search Tree (BST) is a commonly used data structure that can be used to search for an item in O(LogN) time. A BST has the following characteristics: its left nodes are smaller than the root, and its right nodes are larger than the root.

If we perform an inorder traversal—left nodes first, then the current node, and finally right nodes—we will get a fully sorted sequence.

inorder-traversal-of-a-bst

To find the Predecessor or Successor Node of a BST, we can perform the following algorithms:

predecessor-and-successor-of-a-bst

Find the Predecessor Node of a Binary Search Tree (with parent pointer)

The predecessor node is the largest node smaller than the current node.

Correct algorithm with parent pointer:

• If the node has a left child, the predecessor is the rightmost node of the left subtree.
• If the node has no left child, move up to its ancestors until you find a node which is the right child of its parent — that parent is the predecessor.
• If the node is the minimum in the BST, there is no predecessor.

C++ function to Find the Predecessor Node of a Binary Search Tree (with a parent pointer):

TreeNode* predecessor(TreeNode* node) {
    if (!node) return nullptr;
    if (node->left) {
        node = node->left;
        while (node->right) node = node->right;
        return node;
    }
    TreeNode* parent = node->parent; // assume BST nodes have parent pointer
    while (parent && node == parent->left) {
        node = parent;
        parent = parent->parent;
    }
    return parent;
}

Find the Successor Node of a Binary Search Tree (with parent pointer)

The successor node is the smallest node larger than the current node.

Correct algorithm with parent pointer:

• If the node has a right child, the successor is the leftmost node of the right subtree.
• If the node has no right child, move up to its ancestors until you find a node which is the left child of its parent — that parent is the successor.
• If the node is the maximum in the BST, there is no successor.

C++ function to find the successor node of a binary search tree (with a parent pointer):

TreeNode* successor(TreeNode* node) {
    if (!node) return nullptr;
    if (node->right) {
        node = node->right;
        while (node->left) node = node->left;
        return node;
    }
    TreeNode* parent = node->parent;
    while (parent && node == parent->right) {
        node = parent;
        parent = parent->parent;
    }
    return parent;
}

Find the Predecessor Node Without Parent Pointer

If your BST nodes do not have parent pointers, you can find the predecessor using the root of the BST:

• If the node has a left child, the predecessor is the rightmost node of the left subtree.
• If the node has no left child, start from the root and search for the node. Track the last node that is smaller than the target node — this is the predecessor.

C++ function to find the Predecessor node of a binary search tree (without a parent pointer):

TreeNode* predecessor(TreeNode* root, TreeNode* node) {
    if (!node) return nullptr;
    if (node->left) {
        node = node->left;
        while (node->right) node = node->right;
        return node;
    }
    TreeNode* pred = nullptr;
    TreeNode* curr = root;
    while (curr) {
        if (node->val > curr->val) {
            pred = curr;
            curr = curr->right;
        } else if (node->val < curr->val) {
            curr = curr->left;
        } else {
            break;
        }
    }
    return pred;
}

Find the Successor Node Without a Parent Pointer

Similarly, to find the successor without a parent pointer:

• If the node has a right child, the successor is the leftmost node of the right subtree.
• If the node has no right child, start from the root and track the last node that is larger than the target node — this is the successor.

C++ function to find the Successor node of a binary search tree (without a parent pointer):

TreeNode* successor(TreeNode* root, TreeNode* node) {
    if (!node) return nullptr;
    if (node->right) {
        node = node->right;
        while (node->left) node = node->left;
        return node;
    }
    TreeNode* succ = nullptr;
    TreeNode* curr = root;
    while (curr) {
        if (node->val < curr->val) {
            succ = curr;
            curr = curr->left;
        } else if (node->val > curr->val) {
            curr = curr->right;
        } else {
            break;
        }
    }
    return succ;
}

Java – Predecessor Without Parent Pointer

public TreeNode predecessor(TreeNode root, TreeNode node) {
    if (node == null) return null;
    if (node.left != null) {
        node = node.left;
        while (node.right != null) node = node.right;
        return node;
    }
    TreeNode pred = null;
    TreeNode curr = root;
    while (curr != null) {
        if (node.val > curr.val) {
            pred = curr;
            curr = curr.right;
        } else if (node.val < curr.val) {
            curr = curr.left;
        } else {
            break;
        }
    }
    return pred;
}

Java – Successor Without Parent Pointer

public TreeNode successor(TreeNode root, TreeNode node) {
    if (node == null) return null;
    if (node.right != null) {
        node = node.right;
        while (node.left != null) node = node.left;
        return node;
    }
    TreeNode succ = null;
    TreeNode curr = root;
    while (curr != null) {
        if (node.val < curr.val) {
            succ = curr;
            curr = curr.left;
        } else if (node.val > curr.val) {
            curr = curr.right;
        } else {
            break;
        }
    }
    return succ;
}

Python – Predecessor Without Parent Pointer

def predecessor(root, node):
    if node is None:
        return None
    if node.left:
        node = node.left
        while node.right:
            node = node.right
        return node
    pred = None
    curr = root
    while curr:
        if node.val > curr.val:
            pred = curr
            curr = curr.right
        elif node.val < curr.val:
            curr = curr.left
        else:
            break
    return pred

Python – Successor Without Parent Pointer

def successor(root, node):
    if node is None:
        return None
    if node.right:
        node = node.right
        while node.left:
            node = node.left
        return node
    succ = None
    curr = root
    while curr:
        if node.val < curr.val:
            succ = curr
            curr = curr.left
        elif node.val > curr.val:
            curr = curr.right
        else:
            break
    return succ

All implementations take O(1) space (excluding recursion stack if used) and O(N) time in the worst case, O(LogN) on average for a balanced BST.

Finding a successor or predecessor is very useful—for example, it is used to delete a node in a binary search tree.

See also: Compute the Inorder Successor of a Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —