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: Getting height of binary search tree without using recursion

  1. #1
    Junior Member
    Join Date
    Nov 2013
    Posts
    5
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Getting height of binary search tree without using recursion

    Hello. I'm stuck on a homework problem and could use some help if someone would be so kind as to help a beginner understand Java. I'm having some trouble trying to get the height of a binary search tree without relying on recursion. I've created a instance field called h to the Node class and I'm supposed to add a statement to the put method below to update the height after inserting a Node object. Can someone help me to understand how I'm supposed to do this?

    public void put(Key key, Value val) {
            if (val == null) {
                delete(key);
                return;
            }
            root = put(root, key, val);
     
        }
     
        private Node put(Node x, Key key, Value val) {
            if (x == null) {
                return new Node(key, val, 1);
            }
            int cmp = key.compareTo(x.key);
            if (cmp < 0) {
                x.left = put(x.left, key, val);
            } else if (cmp > 0) {
                x.right = put(x.right, key, val);
            } else {
                x.val = val;
            }
            x.N = 1 + size(x.left) + size(x.right);
            return x;
        }


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

    Default Re: Getting height of binary search tree without using recursion

    Well, since you added the h field, you should first initialize it to 0 when the tree is first created. Then once a node is added to the tree, increment the height by one. When a node is removed, decrease the height by one.

  3. #3
    Junior Member
    Join Date
    Nov 2013
    Posts
    5
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Getting height of binary search tree without using recursion

    But wouldn't that just give me the total number of nodes? The height is not the same as the total number of nodes. It's the longest path from the root to any child node.

    For instance for the binary search tree below, the height would be 3

    nodes-in-binary-search-tree.png

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

    Default Re: Getting height of binary search tree without using recursion

    Ohhh, gotcha. Height, not size.
    Were you told whether or not the tree is balanced? If it must be balanced then this could be done a bit easier. If not, I'm not too sure I have a solution right off.

  5. #5
    Junior Member
    Join Date
    Nov 2013
    Posts
    5
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Getting height of binary search tree without using recursion

    Quote Originally Posted by Parranoia View Post
    Ohhh, gotcha. Height, not size.
    Were you told whether or not the tree is balanced? If it must be balanced then this could be done a bit easier. If not, I'm not too sure I have a solution right off.


    The tree can be unbalanced. The easiest way to do it would be through recursion like below but we aren't allowed to do it that way:
    public int height() {
            return height(root);
        }
     
        private int height(Node x) {
            if (x == null) {
                return -1;
            }
            return 1 + Math.max(height(x.left), height(x.right));
        }

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

    Default Re: Getting height of binary search tree without using recursion

    Okay, so after thinking for a bit I might have some insight.
    When you add a node, add 1 to the parent's height. This effect should give the bottom row a height of 0 (or 1 depending on how you're counting) and the root node's height would be the height of the tree.

    Hopefully this makes sense. It's been bouncing around in my head for a bit.

  7. #7
    Junior Member
    Join Date
    Nov 2013
    Posts
    5
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Getting height of binary search tree without using recursion

    You're close. However, a node can have two children. So, say for instance that you add a left child; you would then add 1 to the height of it's parent. But, then if you add a right child, you'd add another 1 to the height of the parent, which would be wrong since you've only gone one level down but you added 2 to the height of the parent.

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

    Default Re: Getting height of binary search tree without using recursion

    I knew there had to be something wrong with it. Perhaps you could check if it's the first node being added to the parent before adding to the height.
    So if the parent already has one child, don't add to the height. If it has zero children, add to the height.

  9. The Following User Says Thank You to Parranoia For This Useful Post:

    berserker (November 8th, 2013)

  10. #9
    Junior Member
    Join Date
    Nov 2013
    Posts
    5
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Getting height of binary search tree without using recursion

    Quote Originally Posted by Parranoia View Post
    I knew there had to be something wrong with it. Perhaps you could check if it's the first node being added to the parent before adding to the height.
    So if the parent already has one child, don't add to the height. If it has zero children, add to the height.
    Yes, I think that's the proper strategy. I'll see if I can write out the code and if it works I'll post it here for other users to benefit from. Thanks for your help by the way!

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

    Default Re: Getting height of binary search tree without using recursion

    No problem. Always helps to have someone else to talk a problem through.

Similar Threads

  1. Binary Search Tree Recursion Implementation
    By ambientplanet in forum What's Wrong With My Code?
    Replies: 0
    Last Post: June 8th, 2013, 03:46 PM
  2. Binary Search Tree inorder tree traversal
    By Maukkv in forum What's Wrong With My Code?
    Replies: 17
    Last Post: January 26th, 2013, 05:28 PM
  3. Height of a node in a binary tree
    By ueg1990 in forum Algorithms & Recursion
    Replies: 2
    Last Post: November 19th, 2012, 01:17 AM
  4. Implementing a binary search tree using recursion?
    By computerbum in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 3rd, 2012, 08:21 PM
  5. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 03:58 AM