This post is completed by 1 user

  • 0
Add to List
Hard

42. Inorder Successor in Binary Search Tree Using Parent link

Objective: Given a Binary Search tree in which every node has a link to its parent, find the in-order successor of a node.

What is Inorder Successor: The 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

Example:

 

InOrder Successor example

Approach:

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

There will be 3 cases to solve this problem

Say the node for whose inorder successor needs to be found is x.

Case 1: If the x has a right child then its inorder successor will be the leftmost element in the right subtree of x.

InOrder Successor - Case 1

Case 2: If the x doesn't have a right child then its inorder successor will the one of its ancestors, using parent link keep traveling up till you get the node which is the left child of its parent. Then this parent node will be the inorder successor.

InOrder Successor - Case 2

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

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

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