Hello Friends, In this article I will try to solve the problem to find the inorder successor of a give node in BST 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; }