| 5 | public class Question { |
| 6 | |
| 7 | public static TreeNode inorderSucc(TreeNode n) { |
| 8 | if (n == null) return null; |
| 9 | |
| 10 | // Found right children -> return left most node of right subtree |
| 11 | if (n.parent == null || n.right != null) { |
| 12 | return leftMostChild(n.right); |
| 13 | } else { |
| 14 | TreeNode q = n; |
| 15 | TreeNode x = q.parent; |
| 16 | // Go up until we�re on left instead of right |
| 17 | while (x != null && x.left != q) { |
| 18 | q = x; |
| 19 | x = x.parent; |
| 20 | } |
| 21 | return x; |
| 22 | } |
| 23 | } |
| 24 | |
| 25 | public static TreeNode leftMostChild(TreeNode n) { |
| 26 | if (n == null) { |