Find Successor

Given the root of a binary tree and a node in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null. The successor here means that the node will be traversed next in an inorder manner for the given node value.

Naive solution

The first solution or the simplest solution that comes to mind when solving inorder successor problem is:

  1. Compute the inorder traversal of the binary tree.
  2. Store the results in an array.
  3. Traverse the array to find the target node.
  4. Return the next element in the array if it exists, otherwise return null.

According the the example:

The inorder traversal is computed as:

  • Traverse left subtree.
  • Print / store the value of the current node.
  • Traverse right subtree.
inorderArr = [6, 4, 2, 5, 1, 3]

Now, The successor of node 5 will be 1 Because 1 occurs right next to 5.

Time Complexity

  • O(n) Because we have to inorder traverse the tree and then iterate over the array to find the desired value.

Optimal Approach

To get the inorder successor of a Binary Tree, we need to take care of 3 steps:

  • Right child of node is not NULL. If the right child of the node is not NULL then the inorder successor of this node will be the leftmost node in it's right subtree.
  • Right Child of the node is NULL. If the right child of node is NULL. Then we keep finding the parent of the given target node, such that targetNode.left = x. For example in the above given tree, inorder successor of node 5 will be 1. First parent of 5 is 2 but 2->left != 5. So next parent of 2 is 1, now 1->left = 2. Therefore, inorder successor of 5 is 1.
  • If node is the rightmost node. If the node is the rightmost node in the given tree. For example, in the above tree node 3 is the right most node. In this case, there will be no inorder successor of this node. i.e. Inorder Successor of the rightmost node in a tree is NULL.

Time Complexity:

  • O(h) in average case if the tree is not skewed.
Solve Find Successor on Algochurn

Practice all the solutions below

Practice the most popular front-end questions asked in coding interviews with   Frontend Churn