In-order Successor in BST

Problem is here: https://leetcode.com/problems/inorder-successor-in-bst/
285. Inorder Successor in BST
Medium
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:
  1. If the given node has no in-order successor in the tree, return null.
  2. It's guaranteed that the values of the tree are unique.
As the problem statement implies, you'll be likely dealing with an InOrder traversal technique (to recap: Inorder => left, current, right). Throughout the traversal, keep track of a boolean to tell you that you have found the node with the key - set that flag to true. Next time that you see it as true, you know you have the successor. That's pretty much it. Cheers, ACC.


public class Solution
{
    public TreeNode InorderSuccessor(TreeNode root, TreeNode p)
    {
        bool isNext = false;
        TreeNode successor = null;
        InorderSuccessor(root, p.val, ref isNext, ref successor);
        return successor;
    }

    private void InorderSuccessor(TreeNode node,
                                    int valueSought,
                                    ref bool isNext,
                                    ref TreeNode successor)
    {
        if (node == null) return;
        InorderSuccessor(node.left, valueSought, ref isNext, ref successor);

        if (isNext && successor == null)
        {
            successor = node;
            return;
        }
        else if (node.val == valueSought)
        {
            isNext = true;
        }

        InorderSuccessor(node.right, valueSought, ref isNext, ref successor);
    }
}

Comments

Popular posts from this blog

Golang vs. C#: performance characteristics (simple case study)

Claude vs ChatGPT: A Coder's Perspective on LLM Performance

My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort