Inorder Successor in Binary Tree

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:

   10
  /  \
 5    30
     /  \
   22    35

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

Java

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.