CODEWITHSUNDEEP
javarecursionbinary-search-tree
Andy897
Andy897

Reputation: 7133

finding parent in binary search tree

Here is the code to find parent in Binary search tree. I am not able to understand how is it working, as we are never assigning any value to parent other than null. I an new to recursion. 

public Node findParent(Type data) 
{
    return findParent(data, root, null);
}

public Node findParent(Type x, Node node, Node parent) 
{
    if (node == null) {
        return null;
    } else if (!(node.data == x)) {
        parent = findParent(x, node.left, node);
        if (parent == null) {
            parent = findParent(x, node.right, node);
        }
    }
    return parent;
}

Upvotes: 2

Views: 2783

Answers (2)

Vincent Beltman
Vincent Beltman

Reputation: 2104

Here I put some comments in it. Tell me if it not seems clear. (Recursion is hard to explain)

// The method
public Node findParent(Type x, Node node, Node parent)
{
    // if this node is null, return null, cause this 
    // is not the path you are looking for
    if (node == null) {
        return null;
        // if this is not the node we are looking for,
    } else if (!(node.data == x)) {
        // We look in the left node.
        parent = findParent(x, node.left, node);
        // If its not found parent will be null
        if (parent == null) {
            // So we go look to the right
            parent = findParent(x, node.right, node);
        }
    }
    // Eventually we can return the parent.
    // If this was the node we were looking for,
    // We can return parent without changing it.
    // If it was not, this algorithm searched in its subtrees
    // If its not there than parent is null.
    return parent;
}

Upvotes: 1

Eran
Eran

Reputation: 393771

You are assigning a non null value to parent in the recursive calls :

parent = findParent(x, node.left, node);
                                  ----
parent = findParent(x, node.right, node);
                                   ----

parent is null only in the initial call (since the root of the tree has no parent).

Each call to findParent gets a value (x), a Node (node) and the parent Node of that Node (parent). If that value is found in the Node, parent is returned, otherwise, you search for that value in the left sub-tree, and if it's still not found, you search for it in the right sub-tree.

Upvotes: 1

Related Questions