Find an InOrder Successor of a node in a BST


Find an InOrder Successor of a Node in a BST.


Possible Solution:
The problem is to find an In-Order successor Node of a given node in a BST.
Basically it means : if you are doing an In-Order traversal what would be your next node if a particular node is given to you.
One way is to use a back pointer – which I assume would be trivial.
Other way would be to do the complete in-order traversal algo to find out. Again trivial.
Otherway would be to use the specific BST properties to figure out – which would turn out more optimal.
This could / should do it :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private static IBinaryTreeNode<Integer> findInorderSuccessor(
  IBinaryTreeNode<Integer> requiredTreeNode,
  IBinaryTreeNode<Integer> root) {
  if (root == null)
    return null;
  if (requiredTreeNode.dataEquals(root)) {
    if (root.right() != null) {
      return leftMost(root.right());
    }
    return lastMaxNode;
  }
  if (root.data() < requiredTreeNode.data()) {
    return findInorderSuccessor(requiredTreeNode, root.right());
  }
  lastMaxNode = root;
  return findInorderSuccessor(requiredTreeNode, root.left());
}
private static IBinaryTreeNode<Integer> leftMost(IBinaryTreeNode<Integer> nd) {
  if (nd == null) {
    return null;
  }
  if (nd.left() == null) {
    return nd;
  }
  return leftMost(nd.left());
}
Fully working code can be found here:

0 comments:

Post a Comment