Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 10 of 10

Thread: binarysearchtree traversing

  1. #1
    Junior Member
    Join Date
    Sep 2013
    Posts
    8
    My Mood
    Confused
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Unhappy binarysearchtree traversing

    Hi, I'm trying to figure out how to do this contains method. everything that's in the method is my code. My thinking is: start at root and go in Inorder traversal and use .equals(). Should I even do that? is there a way I can compare the data, since BST will have lower value to left and higher in right child? I'm lost.
    /**
    Searches for a given element in the binary search tree
    @param someElement element to be searched
    @return true - if someElement is found in the tree; false otherwise
    */
    // Complexity: O(h) - where h is the height of the tree. In the worst case it could be O(n).  But on average
    // we can expect a complexity of O(log n)
    public boolean contains( E someElement) {
     
    	Node node1 = root;
    	if(root == someElement)
    		return true;
     
     
    	if(node1.left != null){
    		boolean result = someElement.equals(node1.left);
    		if(result == false){
    			contains((E) node1);
     
    		}
     
    	}
    }


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: binarysearchtree traversing

    Please edit your post and wrap your code with code tags:
    [code=java]
    YOUR CODE HERE
    [/code]
    to get highlighting and preserve formatting.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Sep 2013
    Posts
    8
    My Mood
    Confused
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: binarysearchtree traversing

    done! thanks

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: binarysearchtree traversing

    Is someElement a Node or contained in a Node?
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Sep 2013
    Posts
    8
    My Mood
    Confused
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: binarysearchtree traversing

    Quote Originally Posted by Norm View Post
    Is someElement a Node or contained in a Node?
    I'm pretty sure it's contained in a node.

  6. #6
    Member
    Join Date
    Apr 2012
    Posts
    161
    Thanks
    0
    Thanked 27 Times in 27 Posts

    Default Re: binarysearchtree traversing

    Your best bet might be to use a recursive call on both child nodes.

  7. #7
    Junior Member
    Join Date
    Sep 2013
    Posts
    8
    My Mood
    Confused
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: binarysearchtree traversing

    ok so this is what i have so far. does it make sense??
    	Node node1 = root;
    	boolean result = false;
     
    	if(root == someElement)
    		return true;
    	//go through left
    	if(node1.left != null){
    		result = someElement.equals(node1.left);
    		if(result == false){
    			contains((E) node1.left);
    		}
    	}
    	//go through right
    	if(node1.right != null){
    		result = someElement.equals(node1.right);
    		if(result == false){
    			contains((E) node1.right);
    		}
    return result;
    	}

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: binarysearchtree traversing

    does it make sense??
    Not if someElement is not a Node. The code needs to compare against the contents of a Node.

    Can you make a complete program for testing this method? Build a simple tree and call the method. Add some println() statements for debugging and execute it to see what happens.
    If you don't understand my answer, don't ignore it, ask a question.

  9. #9
    Junior Member
    Join Date
    Sep 2013
    Posts
    8
    My Mood
    Confused
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: binarysearchtree traversing

    Quote Originally Posted by Norm View Post
    Not if someElement is not a Node. The code needs to compare against the contents of a Node.

    Can you make a complete program for testing this method? Build a simple tree and call the method. Add some println() statements for debugging and execute it to see what happens.
    if I cast node1 as <E> will it make a difference?

  10. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: binarysearchtree traversing

    Casting will not make it a Node. You need to look at the API for the Node class and use one of its methods to access its contents which should be the same type as someElement.
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. Replies: 3
    Last Post: February 26th, 2013, 07:00 PM
  2. [SOLVED] Traversing two different linked list
    By Usoda in forum What's Wrong With My Code?
    Replies: 0
    Last Post: March 10th, 2012, 05:48 PM
  3. Traversing ArrayList of superclass, help? :[
    By Zexis in forum Collections and Generics
    Replies: 1
    Last Post: February 12th, 2012, 02:36 AM
  4. [SOLVED] Traversing a tree
    By IAmHere in forum Algorithms & Recursion
    Replies: 3
    Last Post: June 19th, 2011, 09:47 AM
  5. traversing multiple jTabbedPane?
    By dewboy3d in forum AWT / Java Swing
    Replies: 3
    Last Post: October 2nd, 2009, 07:26 PM

Tags for this Thread