CODEWITHSUNDEEP
javabinary-tree
OneMoreError
OneMoreError

Reputation: 7728

Binary Tree is a BST - Why one works and the other doesn't

I ma trying to check if a given Binary Tree is a Binary Search Tree. I am using in order traversal to do so. The idea is while traversing the tree in in order fashion, at each node check if the node value is greater tha the value of the previous noe visited. If not then then it is not a BST.

The question I have is why he first two work and not the third one :

// This works - Implementation 1
--------------------------------
class PrevWrapper
{
    int data = Integer.MIN_VALUE;
}

public boolean isBST()
{
    return isBST(root, new PrevWrapper());
}

private boolean isBST(Node node, PrevWrapper previousElement)
{
    if ( node == null )
    {
        return true;
    }

    if ( !isBST(node.left, previousElement) )
    {
        return false;
    }

    if ( previousElement.data > node.item )
    {
        return false;
    }

    previousElement.data = node.item;
    return isBST(node.right, previousElement);
}

// This works - Implementation 2
--------------------------------
static int lastValue = Integer.MIN_VALUE;

static boolean isBST(Node root)
{
    if ( root == null )
    {
        return true;
    }
    if ( ! isBST(root.left) )
    {
        return false;
    }
    if ( root.item < lastValue )
    {
        return false;
    }
    lastValue = root.item;
    return isBST(root.right);
}

// This does not work - Implementation 3
--------------------------------

private boolean isBST(Node node, Integer previousElement)
{
    if ( node == null )
    {
        return true;
    }

    if ( !isBST(node.left, previousElement) )
    {
        return false;
    }

    if ( previousElement > node.item )
    {
        return false;
    }

    previousElement = node.item;
    return isBST(node.right, previousElement);
}

Please explain. Wh can't I pass an Integer on function call stake that will maintain state ? or is it something that I am doing wrong with the implementation.

Upvotes: 2

Views: 43

Answers (3)

aparna
aparna

Reputation: 333

Although Integer is a wrapper class for integer, it is immutable. So once set, any edits will only create new objects of the kind, just like for Strings. So although implementation 3 tries to change the value of previousElement in the following line and hopes it will pass through to other recursive calls, it doesn't happen because of the way the Integer class works.

previousElement = node.item;

However Implementation 1, where you create a wrapper for the integer, it will maintain state because the class is passed by reference in subsequent recursive calls.

Upvotes: 1

Eran
Eran

Reputation: 393831

If you pass an Integer as an argument to the next recursive call of isBST, it becomes a local variable of that method, and any assignment done to it will not be seen by the caller of the recursive method when it returns.

This behavior is caused by Java being a pass by value language. When you pass a reference type to a method, that method gets a local copy of that reference. It can only change the state of the instance referred by that reference via methods that change its state (assuming it's mutable). That's what you do in the version that has a PrevWrapper parameter.

Upvotes: 0

KeyboardDrummer
KeyboardDrummer

Reputation: 587

In the latest implementation, this piece of code is not doing what you expect it to:

if ( previousElement > node.item )
{
    return false;
}

previousElement here should have the value of the rightmost leaf node of the left subtree, but instead it has the value of the parent node.

Upvotes: 0

Related Questions