Given a BST node, return the node which has value just greater than the given node.
Example:
Given the tree
100
/ \
98 102
/ \
96 99
\
97
Given 97, you should return the node corresponding to 98 as thats the value just greater than 97 in the tree. If there are no successor in the tree ( the value is the largest in the tree, return NULL).
Using recursion is not allowed.
Assume that the value is always present in the tree.
Method 1:
Inorder traversal
Solution 1:
Time: O(n) Space: O(n)
/** * Definition for binary tree * class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode getSuccessor(TreeNode a, int b) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = a; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } if (!stack.isEmpty()) { curr = stack.pop(); if (curr.val > b) { return curr; } curr = curr.right; } } return null; } }
Method 2:
Binary Search
Solution2:
Time: O(n) Space: O(1)
/** * Definition for binary tree * class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode getSuccessor(TreeNode a, int b) { TreeNode next = null; TreeNode curr = a; while (curr != null) { if (curr.val > b) { next = curr; curr = curr.left; } else { curr = curr.right; } } return next; } }