Hello,

I need help with the print function. Everything works fine, but when I run the that function it gives a stack over flow problem. I do not understand why when this print function works fine with the other binary search tree implementations.

public class SplayTree<AnyType extends Comparable<? super AnyType>>
{
  
    public SplayTree( )
    {
        nullNode = new BinaryNode<AnyType>( null );
        nullNode.left = nullNode.right = nullNode;
        root = nullNode;
    }

    private BinaryNode<AnyType> newNode = null;  // Used between different inserts
    

    public void insert( AnyType x )
    {
        if( newNode == null )
            newNode = new BinaryNode<AnyType>( null );
        newNode.element = x;

        if( root == nullNode )
        {
            newNode.left = newNode.right = nullNode;
            root = newNode;
        }
        else
        {
            root = splay( x, root );
			
			int compareResult = x.compareTo( root.element );
			
            if( compareResult < 0 )
            {
                newNode.left = root.left;
                newNode.right = root;
                root.left = nullNode;
                root = newNode;
            }
            else
            if( compareResult > 0 )
            {
                newNode.right = root.right;
                newNode.left = root;
                root.right = nullNode;
                root = newNode;
            }
            else
                return;   // No duplicates
        }
        newNode = null;   // So next insert will call new
    }

 
    public void remove( AnyType x )
    {
        BinaryNode<AnyType> newTree;

            // If x is found, it will be at the root
        root = splay( x, root );
        if( root.element.compareTo( x ) != 0 )
            return;   // Item not found; do nothing

        if( root.left == nullNode )
            newTree = root.right;
        else
        {
            // Find the maximum in the left subtree
            // Splay it to the root; and then attach right child
            newTree = root.left;
            newTree = splay( x, newTree );
            newTree.right = root.right;
        }
        root = newTree;
    }


    public AnyType findMin( ) throws Exception
    {
        if( isEmpty( ) )
            throw new Exception( );

        BinaryNode<AnyType> ptr = root;

        while( ptr.left != nullNode )
            ptr = ptr.left;

        root = splay( ptr.element, root );
        return ptr.element;
    }

    public AnyType findMax( ) throws Exception
    {
        if( isEmpty( ) )
            throw new Exception( );

        BinaryNode<AnyType> ptr = root;

        while( ptr.right != nullNode )
            ptr = ptr.right;

        root = splay( ptr.element, root );
        return ptr.element;
    }


    public boolean contains( AnyType x )
    {
		if( isEmpty( ) )
			return false;
			
        root = splay( x, root );

        return root.element.compareTo( x ) == 0;
    }

    public void makeEmpty( )
    {
        root = nullNode;
    }


    public boolean isEmpty( )
    {
        return root == nullNode;
    }

    private BinaryNode<AnyType> header = new BinaryNode<AnyType>( null ); // For splay
    
 
    private BinaryNode<AnyType> splay( AnyType x, BinaryNode<AnyType> t )
    {
        BinaryNode<AnyType> leftTreeMax, rightTreeMin;

        header.left = header.right = nullNode;
        leftTreeMax = rightTreeMin = header;

        nullNode.element = x;   // Guarantee a match

        for( ; ; )
        {
			int compareResult = x.compareTo( t.element );
			
            if( compareResult < 0 )
            {
                if( x.compareTo( t.left.element ) < 0 )
                    t = rotateWithLeftChild( t );
                if( t.left == nullNode )
                    break;
                // Link Right
                rightTreeMin.left = t;
                rightTreeMin = t;
                t = t.left;
            }
            else if( compareResult > 0 )
            {
                if( x.compareTo( t.right.element ) > 0 )
                    t = rotateWithRightChild( t );
                if( t.right == nullNode )
                    break;
                // Link Left
                leftTreeMax.right = t;
                leftTreeMax = t;
                t = t.right;
            }
            else
                break;
        }	

        leftTreeMax.right = t.left;
        rightTreeMin.left = t.right;
        t.left = header.right;
        t.right = header.left;
        return t;
    }

  
    private static <AnyType> BinaryNode<AnyType> rotateWithLeftChild( BinaryNode<AnyType> k2 )
    {
        BinaryNode<AnyType> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        return k1;
    }

 
    private static <AnyType> BinaryNode<AnyType> rotateWithRightChild( BinaryNode<AnyType> k1 )
    {
        BinaryNode<AnyType> k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        return k2;
    }

  
    private static class BinaryNode<AnyType>
    {
           
        BinaryNode( AnyType theElement )
        {
            this( theElement, null, null );
        }

        BinaryNode( AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt )
        {
            element  = theElement;
            left     = lt;
            right    = rt;
        }

        AnyType element;            // The data in the node
        BinaryNode<AnyType> left;   // Left child
        BinaryNode<AnyType> right;  // Right child
    }

    private BinaryNode<AnyType> root;
    private BinaryNode<AnyType> nullNode;
    

 
    public void printTree( )
    {
        if( isEmpty( ) )
            System.out.println( "Empty tree" );
        else
            printTree( root );
    }
    
    private void printTree( BinaryNode<AnyType> t )
    {
        if( t != null )
        {
            printTree( t.left );
            System.out.println( t.element );
            printTree( t.right );
        }
    }
    
 
    public static void main( String [ ] args ) throws Exception
    {
      
    	
    	SplayTree<Integer> tree = new SplayTree<Integer>();
    	
    	for(int i = 0; i < 3; i ++)
    		
    		tree.insert(i);
    	  tree.printTree(); 
    	
    }
}

I haven't checked your code properly but you're probably doing something wrong in the insert method and print() ends up in an infinite loop.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.