Predecessor and Successor | Practice Easy 0 attempts
GeeksforGeeks ↗

Predecessor and Successor | Practice

Easy TreeBinary TreeDFS GeeksforGeeks

Given a BST and a key, find the inorder predecessor and successor of the key.

Example: BST = [50,30,70,20,40,60,80], key = 65 → predecessor = 60, successor = 70

Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 10^4
  • 1 <= key <= 10^6
Topics
TreeBinary TreeDFS

BST Traversal

function findPreSuc(root, key) {
  let pre = null, suc = null, curr = root;
  while (curr) {
    if (curr.val < key) { pre = curr; curr = curr.right; }
    else curr = curr.left;
  }
  curr = root;
  while (curr) {
    if (curr.val > key) { suc = curr; curr = curr.left; }
    else curr = curr.right;
  }
  return [pre, suc];
}

Time: O(h) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript