Predecessor and Successor | Practice Easy 0 attempts
GeeksforGeeks ↗

Predecessor and Successor | Practice

Easy TreeBinary TreeDFS GeeksforGeeks

You're given a binary search tree along with a key value. Find that key's inorder predecessor (the largest value smaller than the key) and its inorder successor (the smallest value larger than the key).

Return [predecessorNode, successorNode]; use null for a missing predecessor or successor. The key need not occur in the tree.

Input Format
Implement findPreSuc(root, key). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement. Return [predecessorNode, successorNode]; the editor displays their values or null.

Sample Input and Output

Example 1 ยท Run Sample

Input
root = [50,30,70,20,40,60,80]
key = 65
Output
[60,70]

Example 2

Input
root = [1]
key = 1
Output
[null,null]
Constraints
  • 1 <= N <= 10^4
  • 1 <= key <= 10^6
Test Cases (2)
Case 1
Args: [[50,30,70,20,40,60,80],65] Expected: [60,70]
Case 2
Args: [[1],1] Expected: [null,null]
Topics
TreeBinary TreeDFS

BST Traversal

javascript
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