CODEWITHSUNDEEP
javabinary-treebinary-search-tree
Raul
Raul

Reputation: 154

How to make this method work for finding the successor in BST?

I wrote a method in Java for the successor of a given node in a BST, but it doesn't work

public Node successor(Node selectedNode) {
    Node current = root;
    while (current.element != selectedNode.element) {
        if (selectedNode.element > current.element) {
            current = current.right;
        } else {
            current = current.left;
        }
    }

    if (current.right != null) {
        return min(current.right);
    } else if (current == max(root)) {
        return new Node(Integer.MAX_VALUE);
    } else {
        Node tmp = current;
        if (current.element < root.element) {
            current = root;
            while (current.left.element > tmp.element) {
                current = current.left;
            }
        } else {
            current = root;
            while (current.right.element < tmp.element) {
                current = current.left;
            }
        }

        return current;
    }
}

And the Node class:

public class Node {
public int element;
public Node left;
public Node right;

public Node(int element) {
    this.element = element;
    this.left = null;
    this.right = null;
}

}

My first idea was to write something like this on the else if block, after checking current.right != null:

Node p = t.parent
while(p != null and t == p:right)
    t = p
    p = p:parent
return p

But doesn't work.

Upvotes: 0

Views: 60

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59174

There are two cases:

  1. If the node has a right child, then its successor is the left-most descendant of the right child, or the child itself if it has no left descendants;
  2. Otherwise, the node's successor is its closest ancestor on the right. If you follow the path from the root to the node, then this is the last one from which you go left.

Upvotes: 1

Related Questions