473,226 Members | 1,559 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,226 software developers and data experts.

finding height of a binary search tree without using recursion

I have been given this interface,
Expand|Select|Wrap|Line Numbers
  1. interface BinarySearchTree {
  2.    public void insert(Integer data);
  3.    public int size();
  4.    public int height();
  5.    public boolean contains(Integer target);
  6. }
  7.  
and I have to implement BST with all these functions. I have implemented the first insert and size like this way -
Expand|Select|Wrap|Line Numbers
  1. class Node {
  2.     Node left, right;
  3.     Integer data;
  4.     Node () {
  5.         left = right = null;
  6.         data = 0;
  7.     }
  8. }
  9.  
  10. public class BSTree extends Node implements BinarySearchTree {
  11.     static Node root;
  12.     static int countNode;
  13.     /**
  14.      * Creates a new instance of BSTree
  15.      */
  16.     public BSTree() {
  17.         root = null;
  18.     }
  19.     public void insert(Integer data) {
  20.         if (root == null) {
  21.             root.data = data;
  22.             countNode++;
  23.         } else {
  24.             Node temp = new Node();
  25.             temp = root;
  26.             while (temp != null) {
  27.                 if (temp.data < data) temp = temp.right;
  28.                 else {
  29.                     temp = temp.left;
  30.                 }
  31.                 temp.data = data;
  32.                 countNode++;
  33.             }
  34.         }
  35.     }
  36.     public int size () {
  37.         return countNode;
  38.     }
  39.  
  40.     public int height() { 
  41.         Node temp = new Node();
  42.         /* could have used these for recursion 
  43.         final boolean flag = true;
  44.         if (flag) */
  45.             temp = root;
  46.         if (temp == null) {
  47.             return 0;
  48.         } else {
  49.         /* would have been easy to find height using this recursion
  50.             return 1 + max(height(temp.left), height(temp.right)); */
  51.         }
  52.     }
  53.  
  54.     public boolean contains (Integer target) {
  55.  
  56.     }
  57.     /**
  58.      * @param args the command line arguments
  59.      */
  60.     public static void main(String[] args) {
  61.  
  62.         BSTree bs = new BSTree();
  63.         bs.insert(12);
  64.         bs.insert(3);
  65.         bs.insert(14);
  66.     }
  67.  
  68. }
  69.  
  70.  
The objective requires that the height be implemented without using an argument. Do you have some ideas?
Jan 6 '08 #1
17 16325
BigDaddyLH
1,216 Expert 1GB
Hint: methods are applied to objects. With your height method, you seem to only want to pass objects as arguments. Hmmm...
Jan 7 '08 #2
Ganon11
3,652 Expert 2GB
Most recursive methods dealing with trees can be written with some loops - try thinking of, in general, what your recursive calls would do, then try to mimic that with loops.
Jan 7 '08 #3
BigDaddyLH
1,216 Expert 1GB
Most recursive methods dealing with trees can be written with some loops - try thinking of, in general, what your recursive calls would do, then try to mimic that with loops.
I didn't see anywhere (other that the topic!) in the original post where the OP was required to write a height function that wasn't recursive, just one that worked!
Jan 7 '08 #4
Ganon11
3,652 Expert 2GB
Guess I read into that by the phrase "The objective requires that the height be implemented without using an argument." Most recursive functions have an argument, though I suppose you could implement the recursion without an argument. Then again, if you did so (at least the way I'm thinking) you may as well just use loops.
Jan 7 '08 #5
JosAH
11,448 Expert 8TB
@OP: you keep a separate variable countNode to keep track of the number of
nodes in the tree. You can do similar things where you keep track of the depth
or height of a node in the nodes themselves. At every insert you can update a
separate variable treeHeight and return its value at any time. That way you don't
need any recursion nor arguments to methods and what else ...

kind regards,

Jos
Jan 7 '08 #6
BigDaddyLH
1,216 Expert 1GB
Expand|Select|Wrap|Line Numbers
  1. static Node root;
  2. static int countNode;
  3. ...
  4.  
  5. public BSTree() {
  6.     root = null;
  7. }
  8. ...
  9. public int size () {
  10.     return countNode;
  11. }
  12.  
I just noticed that the root and the countNode (tree size) fields are static. What happens when you have another tree?
Jan 7 '08 #7
BigDaddyLH
1,216 Expert 1GB
@OP: you keep a separate variable countNode to keep track of the number of
nodes in the tree. You can do similar things where you keep track of the depth
or height of a node in the nodes themselves. At every insert you can update a
separate variable treeHeight and return its value at any time. That way you don't
need any recursion nor arguments to methods and what else ...

kind regards,

Jos
I'm from the compute-don't-cache school (of default behaviours). getSize is easy to write recursively (I hope this isn;t giving away the exercise!):
Expand|Select|Wrap|Line Numbers
  1. public int getSize () {
  2.     return _size(root);
  3. }
  4.  
  5. private static int _size(Node n) {
  6.     return n==null? 0 : _size(n.left) + _size(n.right);
  7. }
Method getHeight is just as easy to write recursively. (I think it's actually much harder to write iteratively, since it is not a simple tail recursion.)

Maybe it's my background (math) but I usually find recursion easier to write and understand than iteration.
Jan 7 '08 #8
JosAH
11,448 Expert 8TB
Expand|Select|Wrap|Line Numbers
  1. static Node root;
  2. static int countNode;
  3. ...
  4.  
  5. public BSTree() {
  6.     root = null;
  7. }
  8. ...
  9. public int size () {
  10.     return countNode;
  11. }
  12.  
I just noticed that the root and the countNode (tree size) fields are static. What happens when you have another tree?
Those variables are static because trees themselves don't move either; when will
people ever learn ...

kind regards,

Jos ;-)
Jan 7 '08 #9
BigDaddyLH
1,216 Expert 1GB
Those variables are static because trees themselves don't move either; when will
people ever learn ...

kind regards,

Jos ;-)
I must have been thinking of Ents
Jan 7 '08 #10
JosAH
11,448 Expert 8TB
I must have been thinking of Ents
How silly: Ents are totally extinct because they were all male. You can use
final static variables for them.

kind regards,

Jos ;-)
Jan 7 '08 #11
JosAH
11,448 Expert 8TB
Maybe it's my background (math) but I usually find recursion easier to write and understand than iteration.
Let's shake hands but the way I read the question was about a non recursive
method and I'm also from the lazy bones camp and I think it's much easier
to cache stuff manipulated in the insert method than to set up explicit stacks
and/or trying to be clever with pointer fiddling etc. Recursive methods are much
easier to handle and implement though; I agree.

kind regards,

Jos
Jan 7 '08 #12
BigDaddyLH
1,216 Expert 1GB
Let's shake hands but the way I read the question was ...
Hear, hear. Now if we weren't on far sides of the world, I would say that calls for a beer!
Jan 7 '08 #13
JosAH
11,448 Expert 8TB
Hear, hear. Now if we weren't on far sides of the world, I would say that calls for a beer!
Me too! No problem though, distance is just a figment of people's imagination and
we can solve this the mathematical way: I buy and drink your beer as well ;-)

kind regards,

Jos
Jan 7 '08 #14
r035198x
13,262 8TB
Me too! No problem though, distance is just a figment of people's imagination and
we can solve this the mathematical way: I buy and drink your beer as well ;-)

kind regards,

Jos
Public drinking is not allowed in the public forums.
Admin.
Jan 8 '08 #15
JosAH
11,448 Expert 8TB
Public drinking is not allowed in the public forums.
Admin.
I wore a brown paper bag over my head so there was nothing public about it. I
looked and acted just like any other law obedient citizen.

kind regards,

Jos ;-)
Jan 8 '08 #16
Expand|Select|Wrap|Line Numbers
  1. static Node root;
  2. static int countNode;
  3. ...
  4.  
  5. public BSTree() {
  6.     root = null;
  7. }
  8. ...
  9. public int size () {
  10.     return countNode;
  11. }
  12.  
  13.  
I just noticed that the root and the countNode (tree size) fields are static. What happens when you have another tree?
Those variables are static because trees themselves don't move either; when will
people ever learn ...

kind regards,

Jos ;-)
Thanks Jos for defending the objective. In this problem we were not assigned to make multiple BSTrees, rather just one tree which would have all these functions. :)

As far as writing a non-recursive (loop-iterative) height function is concerned, I could not come up with any and therefore implemented an overridden recursive function in the same class and called that recursive function from this non-recursive function.

I know that wasn't what I was supposed to do but I didnt have any bright ideas until the very last minute of my submission. Time for a compromise..eh
Jan 8 '08 #17
BigDaddyLH
1,216 Expert 1GB
Thanks Jos for defending the objective. In this problem we were not assigned to make multiple BSTrees, rather just one tree which would have all these functions. :)
I would rethink that, if I were you. You are going out of your way to make your code less general. If you insist on having static data, then all the methods should be made static, and the constructor hidden, because you've given up on a class that is designed to be instantiated.
Jan 8 '08 #18

Sign in to post your reply or Sign up for a free account.

Similar topics

7
by: pembed2003 | last post by:
Hi, I have a question about how to walk a binary tree. Suppose that I have this binary tree: 8 / \ 5 16 / \ / \ 3 7 9 22 / \ / \ / \
4
by: Max | last post by:
Hi guys, did some searching on the topic, but can't find much more then just basic info on binary trees. I need to write a binary tree implementation so that it is always complete. In other words...
4
by: Tarique Jawed | last post by:
Alright I needed some help regarding a removal of a binary search tree. Yes its for a class, and yes I have tried working on it on my own, so no patronizing please. I have most of the code working,...
15
by: Foodbank | last post by:
Hi all, I'm trying to do a binary search and collect some stats from a text file in order to compare the processing times of this program (binary searching) versus an old program using linked...
19
by: ramu | last post by:
Hi, I have, suppose 1000 numbers, in a file. I have to find out 5 largest numbers among them without sorting. Can you please give me an efficient idea to do this? My idea is to put those numbers...
2
by: eSolTec, Inc. 501(c)(3) | last post by:
Thank you in advance for any and all assistance. Is there a way to start, pause and resume a recurrsive search exactly where you left off, say in the registry programmatically? -- Michael Bragg,...
1
by: hn.ft.pris | last post by:
I have the following code: Tree.h defines a simple binary search tree node structure ########## FILE Tree.h ################ #ifndef TREE_H #define TREE_H //using namespace std; template...
9
by: nishit.gupta | last post by:
Can somebody please help me for algorithm for postorder bst traversal without recursion. It should use stack. i am not able to implement it. thnx
2
by: aemado | last post by:
I am writing a program that will evaluate expressions using binary trees. Most of the code has been provided, I just have to write the code for the class functions as listed in the header file....
1
isladogs
by: isladogs | last post by:
The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, Mike...
0
by: veera ravala | last post by:
ServiceNow is a powerful cloud-based platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
0
by: mar23 | last post by:
Here's the situation. I have a form called frmDiceInventory with subform called subfrmDice. The subform's control source is linked to a query called qryDiceInventory. I've been trying to pick up the...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
by: jimatqsi | last post by:
The boss wants the word "CONFIDENTIAL" overlaying certain reports. He wants it large, slanted across the page, on every page, very light gray, outlined letters, not block letters. I thought Word Art...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.