@jamesCherrill : Thank you for your clear cut explanation. My doubt got cleared. I searched everywhere on internet but could not get satisfactory answer.. I got it here..From you! Thanks a ton!!! Cheers !

No, it's not any kind of Java language assumption. println is a method in the PrintStream class. (System.out is an instance of PrintStream). It's overloaded for all kinds of parameters, one of which is char[], and that version prints the array as a single String.
So the behaviour is an arbitrary choice made by the authors of the PrintStream class, that's all.

( All other arrays are handled by the version that takes Object as its parameter, and that version prints the object's toString result, whose default behaviour, inherited from Object, is to return a slightly coded version of the object's type followed by its hash.)

Well, I did it again. I'm always lecturing people to make sure they actually read and understand what's being asked and this time I didn't follow my own advice. On top of all my edits/errors, after re-reading Roger's initial post, I see that the goal of all this was not to return the NODE with the desired rank. Assuming I am reading it right THIS time, Roger actually just needs the key/value at that rank. Now I returned the node itself, so it's quite easy to get the key/value given the node. I'm not sure whether that difference changes the optimal strategy or the O(N).

Anyway, as often happens, I glanced at Roger's post, didn't really read it, assumed I knew what he wanted, then went off and experimented with that since it seemed interesting and I'd never thought about it before. So all in all, it wasn't a waste of time and I sort of learned something. Not sure if it actually helps Roger or not though. :)

I AM interested, however, in knowing whether what I did was considered "cheating" or not and whether anyone knows how to do this at better than O(N^2) worst-case scenario with pure recursion, i.e. without using the global flag or something similar.

Well, no, it's not about actual runtime, so what is the relevance?
There's no "timeit module" in standard Java AFAIK, and you give no link or reference for it, so what's the point?

OK, this one should be OK. :) Again, sorry. Ignore the previous code please. Please note that when I use the term "size", I define it as the number of nodes in a tree, which is the size of a node's left tree plus the size of a node's right tree plus one for itself. I've also heard this refered to as "count".

I believe a node's "rank" is the size (number of elements) of its left tree. It is the equivalent of its array index if you changed the binary tree into an ordered array. A completely unbalanced tree where no node has a right child would be your worst case scenario here, I believe. Thus if you have a decreasing array of ten elements {9,8,7,6,5,4,3,2,1,0} and create the tree by inserting each array element in order, you have a tree where the first inserted node (9) is the root of the tree. 9's left child is 8, 8's left child is 7, etc., with no node having a right child. In this tree, each node's "rank" would be its value. I believe this is what the OP is intending? If so, read on. If not, well, read on anyway but it won't answer the OP's question. :)

Finding the size of a tree is an O(N) task regardless of what shape the tree is. Thus finding the rank of a node is an O(N) task since rank is the size of a node's left tree. Now as far as finding the NODE with rank x in this worst-case scenario, I believe that the normal "select" function algorithm is for a node to find its rank. If its rank is x, it returns itself. If its rank is more than x, if it has a left child, it will make a recursive call to its left child. If it has no left child, it returns null. If its rank is less than x, if it has a right child, it will make a recursive call to its right child. Otherwise it returns null.

Node select(int rank)
{
int left_size = 0;
if(left != null)
{
left_size = left.size();
}
if(rank == left_size)
{
return this;
}
else if(rank < left_size && left != null)
{
return left.select(rank);
}
else if(rank > left_size && right != null)
{
return right.select(rank - (left_size + 1)); // add one for this node
}
return null;
}

Worst case scenario is O(N^2) if the rank looked for is 0 in this completely skewed-left tree since you'd have N calls to select while traversing leftward. Each call has a call to size(), which is of order O(N), so O(N^2) total.

However, I believe we can avoid this problem with a global flag that short-circuits the recursion. It might not be the most elegant solution, but I believe it reduces this task to O(N). Let's have a global flag called rankedNode and an two select functions. One is the initial call. It is called once and it's sole purpose is to set that global flag and call the other select functions. I have it as taking two integer parameters, not one, solely to differentiate it from the other select function. The second parameter, named dummyInt, is not used. Again, it's just to differentiate the two functions. Initial call would be to this two-parameter function at the root node.

Node rankedNode = null; // global flag to prevent recursive calls when node is found
Node select(int dummyInt, int rank)
{
rankedNode = null;
return this.select(rank);
}
Node select(int rank)
{
if(rankedNode != null)
return rankedNode; // short-circuit unneeded recurcion
int left_size = 0;
if(left != null)
{
left_size = left.size();
}
if(rank == left_size)
{
rankedNode = this; // flag itself as the answer
return this;
}
else if(rank < left_size && left != null)
{
return left.select(rank);
}
else if(rank > left_size && right != null)
{
return right.select(rank - (left_size + 1)); // add one for this node
}
return null;
}

EDIT: I am using the term "size" to denote the number of elements, including itself, that a node has in its tree. A node's "size" would be its left tree's size plus its right tree's size + one for itself. Equivalent to the term "count". Just clarifying the terminology I am using.

I believe a node's "rank" is the size (number of elements) of its left tree. It is the equivalent of its array index if you changed the binary tree into an ordered array. A completely unbalanced tree where no node has a right child would be your worst case scenario here, I believe. Thus if you have a decreasing array of ten elements {9,8,7,6,5,4,3,2,1,0} and create the tree by inserting each array element in order, you have a tree where the first inserted node (9) is the root of the tree. 9's left child is 8, 8's left child is 7, etc., with no node having a right child. In this tree, each node's "rank" would be its value. I believe this is what the OP is intending? If so, read on. If not, well, read on anyway but it won't answer the OP's question. :)

Finding the size of a node is an O(N) task regardless of what shape the tree is. Thus finding the rank of a node is an O(N) task since rank is the size of a node's left node. Now as far as finding the NODE with rank x in this worst-case scenario, I believe that the normal "select" function algorithm is for a node to find its rank. If its rank is x, it returns itself. If its rank is more than x, if it has a left child, it will make a recursive call to its left child. If it has no left child, it returns null. If its rank is less than x, if it has a right child, it will make a recursive call to its right child. Otherwise it returns null.

Worst case scenario is O(N^2) if the rank looked for is 0 in this completely skewed-left tree since you'd have N calls to select while traversing leftward. Each call has a call to size(), which is of order O(N), so O(N^2) total.

However, I believe we can avoid this problem with a global flag that short-circuits the recursion. It might not be the most elegant solution, but I believe it reduces this task to O(N). Let's have a global flag called rankedNode and an two select functions. One is the initial call. It is called once and it's sole purpose is to set that global flag and call the other select functions. I have it as taking two integer parameters, not one, solely to differentiate it from the other select function. The second parameter, named dummyInt, is not used. Again, it's just to differentiate the two functions. Initial call would be to this two-parameter function at the root node.

... after seeing another post by Teme64 I would have to qualify my previous post by saying I was assuming a balanced tree. In the worst case of an unbalanced tree you have effectively a linked list, and it would be O(N)

Binary search is the subject of another post by OP, but this one is about simply counting all the nodes, so let's not get distracted. Gribouillis is right, although I think the precision of the calculation is not an issue - as long as it's of the form aN+b then the answer is O(N).

@Assert_null : So you trying to say that this unique behaviour of char array in java can be justified by the assumption that in JAVA displaying an array of characters means displaying them as a string.

I'll take a shot. I'm not as familiar as some other people, so please excuse any inarticulate phrasing regarding "reference" or "address", but hopefully it's clear enough.

No for-loop is needed to print the array elements. Java providestoString() methods in the Arrays class. There could be a for-loop "under the hood" there. See code below. As far as why it prints jibberish when you don't use the Arrays.toString() method, that is because it does not assume that it knows what you want so it prints a reference or a memory location or something like that. It's not exactly "jibberish", but it definitely does not display the contents of the array. As for why it prints 'abcd' when you print charArray below, I'm not positive but I believe that the Java implementors just decided to implement that as the default behavior because a character as opposed to anything else is the only array where it makes sense that that's what you want. If you look at the PrintStream class, it has a println(char[]) function. No other array type has that. System.out.println uses the PrintStream class somehow, I believe. I go warnings when compiling to make me aware of that. Tried to copy and paste the exact warning here, but for some reason could not on NetBeans. So basically, I think the underlying assumption in Java, as elsewhere (i.e. C) is that, unless specified otherwise, displaying an array of characters means displaying them as a string. Using the toString() method means display the reference/address of the array. Arrays.toString() means loop through the array and display each element, separated by a comma.

You didn't link the other post you read, so I cannot comment.

Nevertheless, 2N+1 calls exactly is a more precise result than O(N). There is no best case or worst case in this function in terms of number of calls. There is a best and worst case in terms of the length of the stack, but it is another question.

Worst case happens when a binary tree with N nodes is fully biased to left (or right). In your code, null check is always same, that is, it takes a constant time and therefore recursive call to rSize(node.right) takes a constant time. Recursive call rSize(node.left) (or rSize(node.right)) traverses to the "bottom node" i.e. that makes it O(N) to reach the leaf node. You can ignore constant values mentioned above because they are just some constant value c and O(cN) is equal to O(N).

The best case with N nodes is not O(1). You have the "fastest" binary search tree when N nodes are evenly distributed. That means that the height of the binary search three is as small as possible. In this case, to traverse from root node to any leaf node takes O(log N) time because O(log N) is also the height of the binary tree.

Guys I recently discovered that char array can also be printed in java without for loop and the output is a string.But when i tried the same for int array, I got some gibberish value which i though to be memory address pointed by array as it contains reference to the array elements. I read the explanation given by one of the the programmer here but somehow I did not actually understand it.. Could anyone please explain it in a better way ??

When Apple adopt new technologies they usually do it hard and fast. Don't be surprised to see new hardware or software features getting support in Swift first, then before too long, in Swift only.
I say switch too.

For a tree with N nodes, the function will be called exactly 2N+1 times in my opinion (N times with a real node and N+1 times with a null node). You can prove this by induction on N by adding a leaf to a tree or by using the induction hypothesis on each of the two subtrees.

Imports System.IO
Public Class Form1
Dim path As String = "C:\Test\Copiers"
Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
' Create the list to use as the custom source and syve to file
Dim mytext As String = File.ReadAllText(path & "\ test.txt")
'create the source mytxt is the saved file we split to generate an array of string
'str() is the array we useas the source
Dim str() As String = mytext.Split(","c)
Dim MySource As New AutoCompleteStringCollection()
MySource.AddRange(str)
' Create and initialize the text box.
With TextBox1
.AutoCompleteCustomSource = MySource
.AutoCompleteMode = AutoCompleteMode.SuggestAppend
.AutoCompleteSource = AutoCompleteSource.CustomSource
End With
End Sub
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Application.Exit()
End Sub
Private Sub Button2_Click(sender As Object, e As EventArgs) Handles Button2.Click
Dim mytxt As String = ""
Dim myfile As System.IO.StreamWriter
If Directory.Exists(Path) Then
Debug.Print("That path exists already.")
Else
Dim di As DirectoryInfo = Directory.CreateDirectory(Path)
Debug.Print("The directory was created successfully")
End If
mytxt = TextBox2.Text & "," & TextBox3.Text & "," & TextBox4.Text
Debug.Print(mytxt)
myfile = My.Computer.FileSystem.OpenTextFileWriter(Path & "\ test.txt", True)
myfile.WriteLine(mytxt)
myfile.Close()
End Sub
End Class