## Problem Statement

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

## Sample Test Case

Input: root = [2,1,3], p = 1 2 / \ 1 3 Output: 2 Input: root = [5,3,6,2,4,null,null,1], p = 6 5 / \ 3 6 / \ 2 4 / 1 Output: null

## Problem Solution

A node’s inorder successor is node with least value in its right subtree i.e. its right subtree’s left most child.

If right subtree of the node doesn’t exists, then inorder successor is one of the ancestors of it.

To find which ancestor is the successor we can go up from the bottom of the tree towards the root until we encounter a node which is left child of it’s parent. If any such node is found, the inorder successor is its parent else inorder successor do exists for that node.

We can iteratively check above conditions. The idea is to search for given node in the tree and update the successor to current node before visiting its left subtree.

If node is found in the BST, then we return least value node in its right subtree and if the right subtree of the node doesn’t exists, the inorder successor is one of the ancestors of it which is already been updated while searching for the given key.

## Complexity Analysis

Time Complexity: O(h), where h is the height of the tree.

there could be a case (suppose skewed tree) in which we have to travel all the way towards the root.

Space Complexity: O(1) as we are not using any new data structure to store.

## Code Implementation

#include<iostream> using namespace std; class Node { public: int data; Node *left; Node *right; }; //Function to find some data in the tree Node* Find(Node*root, int data) { if(root == NULL) return NULL; else if(root->data == data) return root; else if(root->data < data) return Find(root->right,data); else return Find(root->left,data); } //Function to find Node with minimum value in a BST Node* FindMin( Node* root) { if(root == NULL) return NULL; while(root->left != NULL) root = root->left; return root; } //Function to find Inorder Successor in a BST Node* Getsuccessor( Node* root,int data) { // Search the Node - O(h) Node* current = Find(root,data); if(current == NULL) return NULL; if(current->right != NULL) { //Case 1: Node has right subtree return FindMin(current->right); // O(h) } else { //Case 2: No right subtree - O(h) Node* successor = NULL; Node* ancestor = root; while(ancestor != current) { if(current->data < ancestor->data) { successor = ancestor; // so far this is the deepest node for which current node is in left ancestor = ancestor->left; } else ancestor = ancestor->right; } return successor; } } //Function to visit nodes in Inorder void Inorder(Node *root) { if(root == NULL) return; Inorder(root->left); //Visit left subtree cout<<root->data; //Print data Inorder(root->right); // Visit right subtree } // Function to Insert Node in a Binary Search Tree Node* Insert(Node *root,char data) { if(root == NULL) { root = new Node(); root->data = data; root->left = root->right = NULL; } else if(data <= root->data) root->left = Insert(root->left,data); else root->right = Insert(root->right,data); return root; } int main() { /*Code To Test the logic Creating an example tree 5 / \ 3 10 / \ \ 1 4 11 */ Node* root = NULL; root = Insert(root,5); root = Insert(root,10); root = Insert(root,3); root = Insert(root,4); root = Insert(root,1); root = Insert(root,11); //Print Nodes in Inorder cout<<"Inorder Traversal: "; Inorder(root); cout<<"\n"; // Find Inorder successor of some node. Node* successor = Getsuccessor(root,1); if(successor == NULL) cout<<"No successor Found\n"; else cout<<"Successor is "<<successor->data<<"\n"; }