Find Successor

Tags

Find Successor

Category

Binary Trees

Difficulty

Medium

Problem Statement

Given a binary tree and a target node, find the in-order successor of the target node. The in-order successor is the node that comes immediately after the target node in an in-order traversal of the tree. Each node has a pointer to its parent. If the target is the last node in the in-order traversal, return null.

Intuition

There are two cases for finding the in-order successor:

  1. If the node has a right subtree, the successor is the leftmost node in that right subtree.
  2. If the node has no right subtree, the successor is the nearest ancestor for which the node is in its left subtree. We travel up through parent pointers until we find an ancestor where we came from the left child.

Approach

  1. If the target node has a right child: a. Move to the right child. b. Keep moving to the left child until there are no more left children. c. That node is the successor.
  2. If the target node has no right child: a. Move to the parent. b. Keep moving up while the current node is the right child of its parent. c. The parent at which we stop (where we came from the left) is the successor. d. If we reach the root without finding such a parent, the node has no successor.

Pseudocode

function findSuccessor(tree, node):
    if node.right is not null:
        return getLeftmostChild(node.right)
    return getRightmostParent(node)

function getLeftmostChild(node):
    current = node
    while current.left is not null:
        current = current.left
    return current

function getRightmostParent(node):
    current = node
    while current.parent is not null and current == current.parent.right:
        current = current.parent
    return current.parent  // could be null if no successor

Time & Space Complexity

  • Time: O(h) where h is the height of the tree. In the worst case, we traverse from a leaf up to the root or from a node down to the deepest leaf of a subtree.
  • Space: O(1) - no extra data structures are used; we only follow pointers.

Key Insights

  • The parent pointer is what allows the O(h) time, O(1) space solution. Without it, we would need an O(n) in-order traversal.
  • The two cases (has right child vs. does not) cover all possibilities exhaustively.
  • This algorithm does not require searching for the node first; it starts directly from the given node reference.
  • The same logic applies to any BST or general binary tree, since in-order successor depends on tree structure, not values.

Edge Cases

  • Node is the rightmost (largest in BST) node: has no successor, return null.
  • Node is the root with a right subtree: successor is the leftmost node of the right subtree.
  • Node is a left child leaf: successor is its parent.
  • Node is a right child leaf: successor is the first ancestor where the path goes left.
  • Tree with only one node: no successor exists.
  • Node is the root with no right child: no successor (it is the last in in-order).

Linked mentions