This post is completed by 1 user Login To Mark Completed

0

Add to List Add To List..(Max 5) Close Save

Hard

Inorder Successor in Binary Search Tree without Using Parent link

Objective: Given a Binary Search tree, find the inorder successor of a node.

What is Inorder Successor: Inorder successor of a node is the next node in the inorder traversal of the tree. For the last node in a tree, inorder successor will be NULL

Similar Problems :
Inorder Successor in Binary Search Tree with parent link
Inorder Successor in Binary Tree

Input: A binary search tree, a node x

Output: Inorder successor of node x.

Example:

Approach:

Time Complexity : O(h) , h - height of the tree

There will be 3 cases to solve this problem

Say the node for which inorder successor needs to be find is x.

Case 1 : If the x has a right child then its inorder successor will the left most element in the right sub tree of x.

Case 2: If the x doesn't have a right child then its inorder successor will the one of its ancestors, use the binary search technique to find the node x, start from the root, if root is bigger than the x then go left, if root is less than x, go right. while traveling whenever you go left , store the node and call it successor.

Case 3: if x is the right most node in the tree then its inorder successor will be NULL.

Run This Code

Code:

Tree : 3 5 7 10 17 15
InOrder Successor of 7 is 10
InOrder Successor of 10 is 17

---

---

Also Read:

- Given an array, find all unique subsets with a given sum with allowed repeated digits. Medium
- Maximum Subarray OR Largest Sum Contiguous Subarray Problem – Divide and Conquer Hard
- Merge Sort - Updated - Most Efficient ways to Implement Medium
- Print All Paths From Root In a Binary Tree Whose Sum is Equal to a Given Number Medium
- Inorder Successor in Binary Tree Medium
- Level Order Traversal, Print each level in separate line. Medium
- Number of Islands using BFS Medium
- Find the number of distinct Islands OR connected components. Hard

---