Inorder Successor and Predecessor
Construction and Iterator Patterns DSA practice problem on Onlearn.
Difficulty: medium.
Topics: What are the methods to find the Inorder Successor or Predecessor of a given node in a Binary Search Tree (BST), and how do they work?, Binary Search Tree, Tree Traversal, In-order Traversal, Binary Tree, Iteration, Time Complexity, Space Complexity, Node, inorder traversal, node properties, tree operations, binary search tree, tree traversal, Inorder Successor/Predecessor, Iterative vs. Recursive Approaches, LCA in BST.
Inorder Successor and Predecessor in a Binary Search Tree Problem Statement Given the root of a Binary Search Tree (BST) and an integer val representing the value of a node p within the BST, find the value of p's inorder successor and inorder predecessor. The inorder successor of a node p is the node with the smallest key greater than p.val. The inorder predecessor of a node p is the node with the largest key smaller than p.val. If the inorder successor or predecessor does not exist, indicate it with 1. You can assume that val is present in the BST and all node values are unique. Input Format The input will conceptually consist of: 1. A serialized representation of the Binary Search Tree (e.g., level order traversal where null signifies no child). 2. An integer val, representing the value of the node p for which to find the successor and predecessor. (Note: In a competitive programming setting, a TreeNode class would typically be provided or you would implement it.) Output Format Print two integers separated by a space: the inorder successor's value and the inorder predecessor's value. If either does not exist, print 1 for that value. Constraints The number of nodes in the tree is in the range [1, 10^4]. 10^9 <= Node.val <= 10^9 10^9 <= val <= 10^9 val is guaranteed to be present in the BST. All Node.val are unique. Sample Test Cases Example 1 Input: Tree: [50, 30, 70, 20, 40, 60, 80] val: 40 Output: 50 30 Explanation: For the node with value 40: The inorder traversal of the given BST is: 20, 30, 40, 50, 60, 70, 80. The successor of 40 is 50. The predecessor of 40 is 30. Example 2 Input: Tree: [50, 30, 70, 20, 40, 60, 80] val: 20 Output: 30 1 Explanation: For the node with value 20: The inorder traversal of the given BST is: 20, 30, 40, 50, 60, 70, 80. The successor of 20 is 30. The predecessor of 20 does not exist as it is the minimum value in the BST. Example 3 Input: Tree: [50, 30, 70, 20, 40, 60, 80] val: 80 Output: 1 70 Explanation: For the node with value 80: The inorder traversal of the given BST is: 20, 30, 40, 50, 60, 70, 80. The successor of 80 does not exist as it is the maximum value in the BST. The predecessor of 80 is 70.