Problem

Find Inorder Successor in Binary Tree. OR Given a Binary tree, find the inorder successor of a node.

Definition

See the definition here.

Examples

Example 1:

1
2
3
4
5

   10
  /  \
 5    30
     /  \
   22    35

1
2

Input: root = [10,5,30,null,null,22,35], node = 22
Output: 30

Similar Problems

Inorder Successor in Binary Search Tree Using Parent link Inorder Successor in Binary Search Tree

Solution

Method 1 - Inorder Traversal

To find the in-order successor of a node in a general binary tree (not necessarily a binary search tree), we need to perform an in-order traversal and keep track of the last visited node. The in-order successor of a node is the node that comes immediately after it in an in-order traversal of the tree.

Here are the steps we can follow:

  1. In-order Traversal: Perform an in-order traversal of the binary tree.
  2. Track Last Visited Node: Keep track of the last visited node.
  3. Identify Successor: When the current node matches the target node, the next node visited will be its in-order successor.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public class Solution {

	private TreeNode inorderSuccessor = null;

	private boolean found = false;

	public TreeNode findInorderSuccessor(TreeNode root, TreeNode p) {
		inorderHelper(root, p);
		return inorderSuccessor;
	}

	private void inorderHelper(TreeNode node, TreeNode p) {
		if (node == null) {
			return;
		}

		// Traverse left subtree
		inorderHelper(node.left, p);

		// Check if the previous node was the target node
		if (found) {
			inorderSuccessor = node;
			found = false; // Reset found flag
			return;
		}

		// If current node is the target node, set found flag
		if (node == p) {
			found = true;
		}

		// Traverse right subtree
		inorderHelper(node.right, p);
	}
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the tree. This is because we perform an in-order traversal of the entire tree.
  • 🧺 Space complexity: O(h), where h is the height of the tree. This is due to the recursive call stack used in the in-order traversal. In the worst case, the space complexity can be O(n) for a skewed tree.