## Introduction

Before diving into our topic, “In order Successor of a given key In Binary Search Tree.” Let’s first understand basic terms related to our topic.

Also see, Data Structures

## What is an inorder successor of a BST?

Inorder traversal is a method used to visit every node in a binary tree, where the left subtree is visited first, then the current node, and finally the right subtree. This algorithm is used to traverse binary search trees, and it allows the nodes to be visited in a specific order, useful for various applications.

It is one of the ways to traverse the given binary tree such that the elements are ordered in such a way that the left node comes before the root node, and the right node comes after the root node.

**LEFT -> ROOT -> RIGHT**

We can remember this by the keyword ‘IN’, meaning that the root node should come** in between** the left and right nodes.

Similarly, in pre-order and post-order, the root node should come ‘PRE’** (before left node) **and **‘**POST’** (after right node), **respectively.

OKAY, now that the inorder traversal is clear, let’s see the main properties of Binary Search Trees.

A Binary Search Tree is a Binary Tree (obviously), so in BSTs, each node can have at most two children. But BSTs also have one interesting property: each node in a BST** is greater than the maximum node in its left subtree** and **lesser than the minimum node in its right subtree.**

**Let’s see an example:**

If we observe the given Binary Tree, we can tell that it is a Binary Search Tree because the value of each node is greater than the maximum valued node in its left subtree and is lesser than the minimum valued node in its right subtree.

For instance, take node 50, the maximum valued node in its left subtree is 45, and the minimum valued node in its right subtree is 55.

If we print the Inorder Traversal for this BST, we’ll get:

**10 35 40 45 50 55 70 100 150**

See, the elements are in ascending order. That brings us to another interesting fact related to BSTs: the** inorder traversal of a BST gives us elements in ascending order sorted manner.**

NOW, coming on to the main topic of this blog, “Inorder Successor of a given key In Binary Search Tree.”

**The Inorder Successor of a given key in the Binary Search Tree is the node that appears just after the provided key node in the inorder traversal of the BST.**

From our above example, we can say that the Inorder Successor of, let’s say, 35 is 40 because, in the inorder traversal of BST, it is coming just after 35. For 50, it will be 55, and so on.

Kudos! Now you have understood all the essential things needed, and the only thing left is to write code to find the in-order successor of a given key In the Binary Search Tree.

**Recommended:** Try The Problem yourself before moving on to the solution.