How should I practice Inorder Successor in a Binary Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is Inorder Successor in a Binary Tree associated with Microsoft?

FastPrep tags this as a Microsoft online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Inorder Successor in a Binary Tree

Learn this problem

● Hard

MicrosoftINTERNOA

See Microsoft hiring insights

Problem statement

You are given the root root of a non-empty binary tree and an integer targetValue. Every node has a unique non-negative integer value, and exactly one node has value targetValue.

Return the value of the node that appears immediately after the target node in an inorder traversal. An inorder traversal visits the left subtree, then the node, then the right subtree. If the target is the final node in that traversal, return -1.

Your algorithm must use O(1) auxiliary space. Do not use recursion, an explicit stack, or another auxiliary collection. You may temporarily redirect right-child pointers while traversing, but every pointer must be restored before the function returns.

Function

findInorderSuccessor(root: TreeNode, targetValue: int) → int

Examples

Example 1

root = [8,4,2,null,6,1,3]targetValue = 8return = 1

The inorder sequence is [4, 6, 8, 1, 2, 3]. The node after 8 has value 1. This example also shows that the input is a general binary tree, not necessarily a binary search tree.

Example 2

root = [20,10,30,5,15,25,35]targetValue = 15return = 20

The inorder sequence is [5, 10, 15, 20, 25, 30, 35], so the successor of 15 is 20.

Example 3

root = [4,2,6,1,3,5,7]targetValue = 7return = -1

The target value 7 is the final value in inorder traversal, so it has no successor.

Constraints

The tree contains between 1 and 10^5 nodes.
0 <= Node.val <= 10^9.
All node values are distinct.
targetValue equals the value of exactly one node in the tree.
The input is one finite, acyclic binary tree.
The solution must use O(1) auxiliary space without recursion, an explicit stack, or another auxiliary collection.
Every temporary pointer change must be restored before the function returns.