285. Inorder Successor in BST
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
The successor of a node p is the node with the smallest key greater than p.val.
Example 1:
Input: root = [2,1,3], p = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.
Example 2:
Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.
Note:
- If the given node has no in-order successor in the tree, return
null. - It's guaranteed that the values of the tree are unique.
---
Related problems
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Definition for a binary tree node. | |
| * public class TreeNode { | |
| * int val; | |
| * TreeNode left; | |
| * TreeNode right; | |
| * TreeNode(int x) { val = x; } | |
| * } | |
| */ | |
| public class Solution { | |
| /* | |
| * @param root: The root of the BST. | |
| * @param p: You need find the successor node of p. | |
| * @return: Successor of p. | |
| */ | |
| public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { | |
| TreeNode ans = null; | |
| while (root != null) { | |
| if (root.val > p.val) { | |
| // Save potential ans, continue looking for better ans < root | |
| ans = root; | |
| root = root.left; | |
| } else { | |
| root = root.right; | |
| } | |
| } | |
| return ans; | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Definition for a binary tree node. | |
| * public class TreeNode { | |
| * int val; | |
| * TreeNode left; | |
| * TreeNode right; | |
| * TreeNode(int x) { val = x; } | |
| * } | |
| */ | |
| public class Solution { | |
| /* | |
| * @param root: The root of the BST. | |
| * @param p: You need find the successor node of p. | |
| * @return: Successor of p. | |
| */ | |
| public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { | |
| if (root == null) { | |
| return null; | |
| } | |
| if (root.val > p.val) { | |
| // Found possible ans, search for better one | |
| TreeNode left = inorderSuccessor(root.left, p); | |
| // If we find better ans, return that, else return currrent root | |
| return left == null ? root : left; | |
| } else { | |
| // Invalid root <= p, search in higher half | |
| return inorderSuccessor(root.right, p); | |
| } | |
| } | |
| } |
