/285. Inorder Successor in Binary Search Tree
Previous|Next

285. Inorder Successor in Binary Search Tree

Medium
Trees51.2% acceptance

Given the root node of a binary search tree and a target node, return the node that is the inorder successor of the target node. The inorder successor is defined as the node with the smallest key greater than the target node's key. If the target node has no inorder successor, return None.

Example 1

Input: root = TreeNode(8) root.left = TreeNode(3) root.right = TreeNode(10) root.left.left = TreeNode(1) root.left.right = TreeNode(6) root.left.right.left = TreeNode(4) root.left.right.right = TreeNode(7) root.right.right = TreeNode(14) root.right.right.left = TreeNode(13) target = root.left.right.left # Node with value 4 find_inorder_successor(root, target)

Output: root.left.right # Node with value 6

Explanation: The inorder successor of node 4 is node 6.

Example 2

Input: root = TreeNode(20) root.left = TreeNode(9) root.right = TreeNode(25) root.left.left = TreeNode(5) root.left.right = TreeNode(12) root.left.right.left = TreeNode(11) root.left.right.right = TreeNode(14) target = root.left.right.right # Node with value 14 find_inorder_successor(root, target)

Output: root # Node with value 20

Explanation: The inorder successor of node 14 is node 20.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4].
  • All node values are unique integers.
  • The target node is guaranteed to be present in the tree.
Python (current runtime)

Case 1

Input: root = TreeNode(15) root.left = TreeNode(6) root.right = TreeNode(18) root.left.left = TreeNode(3) root.left.right = TreeNode(7) root.right.left = TreeNode(17) root.right.right = TreeNode(20) target = root.left # Node with value 6 find_inorder_successor(root, target)

Expected: root.left.right # Node with value 7

Case 2

Input: root = TreeNode(30) root.left = TreeNode(20) root.right = TreeNode(40) root.left.left = TreeNode(10) root.left.right = TreeNode(25) root.right.left = TreeNode(35) root.right.right = TreeNode(50) target = root.right.right # Node with value 50 find_inorder_successor(root, target)

Expected: None