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.)

https://docs.oracle.com/javase/8/docs/api/java/io/PrintStream.html

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.

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.

Node select(int rank)
{
    if(left == null)
    {
        if(rank == 0)
            return this;
         return null;
    }
    int left_size = left.size();
    if(left_size == rank)
        return this;
    else if(rank < left_size)
    {
        return left.select(rank);
    }
    else if(rank > left_size && right != null)
    {
        return right.select(rank - left_size - 1);
    }
    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;

    if(left == null)
    {
        if(rank == 0)
        {
            rankedNode = this;
            return this;
         }
         return null;
    }

    int left_size = left.size();
    if(left_size == rank)
    {
        rankedNode = this;
        return this;
    }
    else if(rank < left_size)
    {
        return left.select(rank);
    }
    else if(rank > left_size && right != null)
    {
        return right.select(rank - left_size - 1);
    }
    return null;
}

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.

    int intArray[] = new int[]{1,2,3,4};
    char charArray[] = new char[]{'a','b','c','d'};
    System.out.println(intArray); // gibberish
    System.out.println(charArray); // abcd
    System.out.println(intArray.toString()); // gibberish
    System.out.println(charArray.toString()); // gibberish
    System.out.println(Arrays.toString(intArray)); // [1, 2, 3, 4]
    System.out.println(Arrays.toString(charArray)); // [a, b, c, d]

JamesCherrill is correct about O(N).

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.

HTH

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 ??

There is good code here how this works. I think you need to rethink your saving of the file and how you load it.
https://msdn.microsoft.com/en-us/library/system.windows.forms.textbox.autocompletemode(v=vs.110).aspx

Here is a complete snippets how it works:

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
Attachments Years.gif 28.4 KB