Inorder Successor
Given a binary search tree root containing unique values, and an integer t, return the value of the inorder successor of t. That is, return the smallest value greater than t in the tree.
Note: you can assume that the inorder successor exists.
Bonus: solve it in O(h)$‘timeand‘$O(1) space where h is the height of the tree.
Constraints
n ≤ 100,000wherenis the number of nodes inroot
https://binarysearch.com/problems/Inorder-Successor
ExamplesPermalink
Example 1Permalink
Input
- root =
- t =
2
Output
- answer =
3
Example 2Permalink
Input
- root =
- t =
1
Output
- answer =
2
SolutionPermalink
This file contains 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
| /** | |
| * class Tree { | |
| * public: | |
| * int val; | |
| * Tree *left; | |
| * Tree *right; | |
| * }; | |
| */ | |
| int solve(Tree *root, int t) | |
| { | |
| int res = INT_MAX; | |
| while (root) | |
| { | |
| if (root->val > t) | |
| { | |
| res = std::min(res, root->val); | |
| root = root->left; | |
| } | |
| else | |
| { | |
| root = root->right; | |
| } | |
| } | |
| return res; | |
| } |
Leave a comment