In Order successor of a node in binary search tree
source link: https://www.dotnetforall.com/in-order-successor-of-a-node-in-binary-search-tree/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Aug 27 2021
In Order successor of a node in binary search tree
Hello Friends, In this article I will try to solve the problem to find the inorder successor of a give node in BSR or binary search tree.
The problem is below and it says:
Write an algorithm to find the “next” node (I.e. in order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.
I have discussed the problem on my you tube channel here:
Ways to Solve In Order successor
There are two ways to solve the problem.
One way is to traverse the binary search tree and store the contents in an array. Find the specific node and return the next element of the array. There are two problems to this approach. I have discussed both of them in the video.
The other way is to check two conditions:
- If the node has a right subtree, get the left most node of the right sub tree.
- Otherwise get the parent whose left sub tree has this node.
class Node{
public Node left;
public Node right;
public Node parent;
}
public Node GetSuccesor(Node node){
{
if(node == null)
return null;
if(node.right != null)
return GetTheLeftMostChildOfRightNode(node.right);
return GetTheParentOfLeftNode(node);
}
public Node GetTheLeftMostChildOfRightNode(Node node){
Node currentNode = node;
while(currentNode.Left != null)
{
currentNode = currentNode.Left;
}
return currentNode;
}
public Node GetTheParentOfLeftNode(Node node){
Node currentNode = node;
while(currentNode != null && currentNode == currentNode.Parent.Right){
currentNode = currentNode.Parent;
}
return currentNode.Parent;
}
Top career enhancing courses you can't miss
My Learning Resource
Excel your system design interview
Like this:
Related
Written by Vikram Chaudhary · Categorized: Daily Coding Problem, Data Structures And Algorithms · Tagged: algorithm, datastructures
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK