Longest decreasing sub-array

[Kaspersky Ukshini]

This is a bit tricky!
I have a given array of numbers, and I have to find the longest decreasing sub-array, but the thing is that the elements don't have to be next to each other!

For example, the longest decreasing sub-array for this array:
546 -156 165 -156 -56 -13 5

is 3 (check the bold numbers)
Until now, I have nearly finished my code, but I have one problem...

private static int decreasing(int[] a) {
int result=1, temp=0, br=1;
//Checking all the elements one by one:
for(int i=0;i<a.length;i++){
temp=a[i]; //placing the element on a temp value
for(int j=i+1;j<a.length;j++) // I start another for cyclys, from the next element of a[i]
{
if(a[j]<temp) // I start comparing if this element is SMALLER than the one I have
{ // if yes, put that element on temp
temp=a[j];
br++; //and rise my counter (to keep track of the length of the decreasing array)
}
}
if(br>result) //when I finish comparing a[i] with all the elements to it's right,
result=br; //i check if the length of the sub-array is longer than the one before
br=1;
}
return result;
}

The problem with this code is that it's not smart.. let's say I have:
100 -500 90 80 70

Once it hits -500, none of the other if's with pass....
Any ideas how to avoid this?

[Knute Snortum]

Do you need to copy the array, or just put the next lower element in an array?

[Kaspersky Ukshini]

I need to count the longest sequence... that's what the function should return..

[fred rosenberger]

have you worked out - on paper - how to do it yourself?

an example is great, but it isn't really a spec. Do you think you could give those directions to a child and they could accurately compute it?

[Kaspersky Ukshini]

 

fred rosenberger wrote:have you worked out - on paper - how to do it yourself?

an example is great, but it isn't really a spec. Do you think you could give those directions to a child and they could accurately compute it?

Dude, honestly! I have nooo clue! ):

[fred rosenberger]

 

Kaspersky Ukshini wrote:Dude, honestly! I have nooo clue! ):

So start thinking about it. sketch some examples. run through some scenarios. start with a small array, and work through it. Then try a slightly larger array. See if you can find a pattern.

Programming is more about teaching yourself how to think through a problem than writing code.

[Kaspersky Ukshini]

1day left for my exam, brain is slowly stopping to work... Just what they like to do before exams lol!

[Piet Souris]

Well, it is too late now, for the upcoming exam and brainstop,
but maybe you could sort the array, from high to low. Of course,
you loose the original positions, and that is very nasty,
but maybe there is a possibility to somehow keep the
original positions.

But even so, what use would all this be ? Hmm...

Greetz,
Piet

[Kaspersky Ukshini]

 

Piet Souris wrote:Well, it is too late now, for the upcoming exam and brainstop,
but maybe you could sort the array, from high to low. Of course,
you loose the original positions, and that is very nasty,
but maybe there is a possibility to somehow keep the
original positions.

But even so, what use would all this be ? Hmm...

Greetz,
Piet

I don't think sorting the list would somehow help...
We may get something similar to this in the exam, it doesn't hurt to learn a new idea, the thing is that in this case, i'm finding it hard to think of something...

[fred rosenberger]

I wonder if recursion would work here...I honestly don't know...but..

546 -156 165 -156 -56 -13 5

so let's find the longest one in the array
546 -156 165 -156 -56 -13

If i know how long it is for that one, can I figure out if adding a 5 to the end improves the score?

[Piet Souris]

 

Kaspersky Ukshini wrote:
I don't think sorting the list would somehow help...
(...)

Well, take Fred's array:

546 -156 165 -156 -56 -13 5

and suppose that we sort it, keeping the original positions.
We get this:

546 0
165 2
5 6
-13 5
-156 1
-156 3

Looking at this, anything that comes up? Take a special look at the original positions.

Greetz,
Piet

[Knute Snortum]

Think about what you would actually do, remembering that the computer is forgetful and stupid.

I start at the first element

I look for the next element that's lower

I write down the elements that are in the subarray

When I get to the end of the original array, I look at the subarray's length

There might be another subarray, so I start at the second element of the original array

I do the above steps again

I check if my new subarray is longer than the other subarray

...Are you getting the idea?

[Kaspersky Ukshini]

 

Knute Snortum wrote:Think about what you would actually do, remembering that the computer is forgetful and stupid.

I start at the first element

I look for the next element that's lower

I write down the elements that are in the subarray

When I get to the end of the original array, I look at the subarray's length

There might be another subarray, so I start at the second element of the original array

I do the above steps again

I check if my new subarray is longer than the other subarray

...Are you getting the idea?

That's what I already wrote before creating this topic, but it didn't work for all cases... cause the sub arrays doesn't have to be one after another.. I can start making my array from the first element, then jump to the 3rd, then 5th... JUST RIGHT.... that's what makes it harder, but nvm, I guess I found the solution...

Piet Souris wrote:

Kaspersky Ukshini wrote:
I don't think sorting the list would somehow help...
(...)

Well, take Fred's array:

546 -156 165 -156 -56 -13 5

and suppose that we sort it, keeping the original positions.
We get this:

546 0
165 2
5 6
-13 5
-156 1
-156 3

Looking at this, anything that comes up? Take a special look at the original positions.

Greetz,
Piet

Ohhh.... Nowwwwwwwwwwwwww I see!
After sorting it, I start looking for the longest INCREASING array (in the array of indexes)
LET ME GIVE IT A TRY RIGHT NOWWWWWWW!!

[Kaspersky Ukshini]

Can't seem to be able to SORT the array and keep track of the indexes at the same time :/
This is what I have up untill now:

while(fixed==false){
fixed=true;
for(int i=0;i<a.length-1;i++)
{
if(a[i+1]>a[i]){
b[i]=i+1; // this is a new array where I keep all the indexes,
//the swap:
int tmp=a[i];
a[i]=a[i+1];
a[i+1]=tmp;
fixed=false;
}
}
}

I try printing the new array after the sort,but it's the other way around, plus there is a problem
cause the for loop only goes up until a.length-1 ..so the last member of b[] wont ever be reached..

[Knute Snortum]

This is how I'd do it:

1) I need an array to hold the longest subarray
2) I need an array to hold the subarray I'm looking at
3) Start at the first element in the original array
4) Add the element to my temp array
5) Look at the next element
6) If it's less than the last element in the temp array, add it to the temp array
7) Do this for all elements in the array
8) If the temp array is longer than the longest subarray, copy the temp array to the longest
9) go to 3) but start at the second element
10) do steps 4 thru 8
11) now start at the third element in the original
12) continue like this until you get to the last element, or the longest array is longer than the remaining elements
13) return longest subarray

[Kaspersky Ukshini]

I believe im close.. I've decided to use a new class of arrays, each holding the value and it's index.

class Pair{
private int value;
private int index;
Pair(){
this.value=0;
this.index=0;
}
Pair(int index, int value) {
this.index = index;
this.value = value;
}

Then I'm trying to convert the curent Array into my new one:

public class LDS {
private static int sorting (int[] a) {
Pair[] index=new Pair[a.length];
for(int i=0;i<index.length;i++){
index[i].setValue(a[i]);
index[i].setIndex(i);
}

And NO LUCK! I'm getting this error when trying it: Exception in thread "main" java.lang.NullPointerException

[Junilu Lacar]

 

Piet Souris wrote:But even so, what use would all this be ? Hmm...

I did some searching and apparently it does have practical uses. If you are interested, search terms include "longest increasing subsequence", "longest decreasing subsequence", "Pigeonhole Principle", "Erdős–Szekeres theorem", and "Dynamic Programming". As far as I could tell, one very familiar problem that is related to this kind of math is that of boarding people on a plane as efficiently as possible.

[Winston Gutkowski]

 

Kaspersky Ukshini wrote:I believe im close.. I've decided to use a new class of arrays, each holding the value and it's index.

You might also want to have a look at the Patience sorting algorithm, because it's a lot simpler to follow than the one for LIS (at least for a duffer like me). It also makes perfect sense that that kind of sort would be related to a "longest subsequence" solution.

Indeed, if you only need to return the length of the longest subsequence, I suspect it's also the quickest.

HIH

Winston

PS: It's maybe worth mentioning that there can be more than one "maximal sub-array" in your list.

[Kaspersky Ukshini]

 

Kaspersky Ukshini wrote:I believe im close.. I've decided to use a new class of arrays, each holding the value and it's index.

class Pair{
private int value;
private int index;
Pair(){
this.value=0;
this.index=0;
}
Pair(int index, int value) {
this.index = index;
this.value = value;
}

Then I'm trying to convert the curent Array into my new one:

public class LDS {
private static int sorting (int[] a) {
Pair[] index=new Pair[a.length];
for(int i=0;i<index.length;i++){
index[i].setValue(a[i]);
index[i].setIndex(i);
}

And NO LUCK! I'm getting this error when trying it: Exception in thread "main" java.lang.NullPointerException

Guys, I belive I'm really close, I just need to know why am I getting this stupid error now? Maybe I'm missing a small detail somewhere, while compailing everything is ok....

[Jelle Klap]

Ater you declare and initialize the index array at line 6 it contains only null references.
You then dereference null inside your for-loop by invoking setValue() which results in a NullPointerException.

[Piet Souris]

I must confess that my proposed solution did work for the example given, but it does not work in general,
Besides, it would still be a bit awkward to get the longest sublist.

So I just wrote a much simpler solution, that does not involve any sorting. I have to go now,
but I'll show it later this afternoon.

Greetz,
Piet

[Chan Ag]

I have only tried an algorithm on paper so far. I mean no programming. Just some tree nodes and diagrams. Here's my algorithm.

1. Read one number ( each of those will make one or several tree nodes as we will see ) at a time.
2. For the first number, make it the root node. Store its depth. For the first node it'll be 1. Its parent is null. Store this node as one of the nodes with maximum depth in the maximum depth nodes' array.
3. Read the next number. For each number you read, traverse the tree from the root in the following way.
3.1 If the next number is smaller than or equal to the root number, add the number you read as a sub-tree node of the root. Store its parent as root. Calculate and store the depth of the sub-tree node you added. Update the maximum depth nodes' array.
3.2 If its larger than the root, start another tree with the node you read as the root. (There are some improvements possible as you traverse your trees -- you can ignore some trees -- but I will leave that up to you )
3.11 Now traverse each node at next level (root +1 depth ) referring to that as the current node. For this node also, if the number you have read is smaller than the current node, add the node you have read as its sub tree node. Store its depth and parent and so on...

At the end you have one or more elements in the maximum depth nodes' array. And you can traverse this way to get the sub array -->
the leaf node with maximum depth --> its parent --> its parent's parent ..

I think this should work for all the cases.

[Chan Ag]

 

Chan Ag wrote:
3.2 If its larger than the root, start another tree with the node you read as the root. (There are some improvements possible as you traverse your trees -- you can ignore some trees -- but I will leave that up to you )

I think a better wya to handle this is to create a dummy node with a really high number, say Integer.MAX_VALUE and make all root nodes, its children.

Yes, that should work.

[Winston Gutkowski]

 

Chan Ag wrote:I have only tried an algorithm on paper so far. I mean no programming. Just some tree nodes and diagrams.

I certainly think you're on the right lines; but I doubt that the structure involves just a single root (because there could be more than one "maximal" subsequence) - although, oddly enough, when I was trying to "visualise" it, I was thinking along exactly the same lines and using a heap - I suspect, however, that's it's only part of the solution, not the whole.

The Patience Sort ticks most of the boxes for me: It's simple, familiar, and it's also easy to follow how it's likely to be very strongly related to a "maximal sequence" problem.

Ain't programming fun?

Winston

[Piet Souris]

This Kaspersly with his poblems....

The algorithm I came up with is easy, maybe along the way that Chan describes.
I'll give an example.

Suppose we have the array {4, 8, 2}.

And that we have a List of List<Integer>, called subsequences.

Now, start with the right most element, i.e. 2.

Compare this element to every List in subsequences. If the element
is larger than or equal to the first element of this List, add it
to the List. Finally, add the element to a new List, and add that List
to subsequences.

Then go to the next element to the left, do the same, et cetera,
until we had all elements.

We now have a list of ll subsequnces. Take the largesr in size
and we're done.

For array {4, 8, 2} we would get the following subsequences-list:

{ {2} }
{ {8,2} , {2} , {8}}
{ {8,2}, {4, 2}, {2} , {8} , {4} }

And so the longest subsequence is either {8, 2} or {4, 2}
The only worry is that the number of LinkedLists is increasing at
an alarming rate, about 2^n, which is deadly for any algorithm.
Guess I'll have to do some extra study...

Here's the method:

public class Kaspersky {
public static void main(String... args) {
new Kaspersky().go();
}
//-------------------------------------------------
private void go() {
int[] given = {10, 9, -3 , 5 , 12 , 3 , -4 , -6 , -10 , 8 , 0 };
List<Integer> lijst = getLongestSubsequence(given);
for (int x: lijst) System.out.println(x);
}
//-------------------------------------------------
private List<Integer> getLongestSubsequence(int[] ints) {
ArrayList<LinkedList<Integer>> subsequences = new ArrayList<>();
for (int index = ints.length - 1; index >= 0; index--) {
ArrayList<LinkedList<Integer>> newSubs = new ArrayList<>();
for (LinkedList<Integer> ll: subsequences) {
if (ints[index] >= ll.getFirst()) {
LinkedList<Integer> newlist = new LinkedList<>(ll);
newlist.addFirst(ints[index]);
newSubs.add(newlist);
}
}
LinkedList<Integer> temp = new LinkedList<>();
temp.add(ints[index]);
newSubs.add(temp);
subsequences.addAll(newSubs);
}
Collections.sort(
subsequences, (x, y) ->
x.size() > y.size() ? -1 :
x.size() == y.size() ? 0 :
1
);
return subsequences.get(0);
}
}

[Chan Ag]

 

Winston Gutkowski wrote:I doubt that the structure involves just a single root (because there could be more than one "maximal" subsequence

Thanks. Here's a work around that resulted in a refinement ( I think ).
Let's consider the following sequence.

546 -156 165 -156 -56 -13 5

Read 546

--> 546 parent=null, depth=1, max depth node[] = {546}, max depth = 1




Read -156

--> 546
|
-156 parent = 546, depth =2, max depth node[] = {-156}, max depth = 2




Read 165

--> 546
| |
165 -156-I
parent =546, depth =2, max depth node[] = {-165, 156-I}, max depth = 2
165 also moves to the left cause it is larger than -156-I.



Read -156 (Let this be -156-II)

--> 546
| |
165 -156-I
|
-156-II parent =165, depth =3, max depth node[] = {156-II}, max depth = 3
Can add to -156-I also but for roots of equal depth, pick the left most root cause that's the largest.
Add as the child of the left most node cause we can find any solution as long as it gives the longest sub sequence. This would greatly simplify the design cause we won't require a parent[].





Read -56

--> 546
| |
165 -156-I
| |
-56 -156-II
parent =165, depth =3, max depth node[] = {-56, 156-II}, max depth = 3




Read -13

--> 546
| |
165 -156-I
| | |
-13 -56 -156-II
parent =165, depth =3, max depth node[] = {-13, -56, 156-II}, max depth = 3
Add as the child of the left most node.


Read 5

--> 546
| |
165 -156-I
| | | |
5 -13 -56 -156-II
parent =165, depth =3, max depth node[] = {5, -13, -56, 156-II}, max depth = 3
Add as the child of the left most node.

So we get

546, 165, 5
546, 165, -13
546, 165, -56
546, 165, -156-II


We can return the left most sequence here or (whichever we like ).

I am still working on Piet's solution for longer sequences.

[Kaspersky Ukshini]

 

Kaspersky Ukshini wrote:I believe im close.. I've decided to use a new class of arrays, each holding the value and it's index.

class Pair{
private int value;
private int index;
Pair(){
this.value=0;
this.index=0;
}
Pair(int index, int value) {
this.index = index;
this.value = value;
}

Then I'm trying to convert the curent Array into my new one:

public class LDS {
private static int sorting (int[] a) {
Pair[] index=new Pair[a.length];
for(int i=0;i<index.length;i++){
index[i].setValue(a[i]);
index[i].setIndex(i);
}

And NO LUCK! I'm getting this error when trying it: Exception in thread "main" java.lang.NullPointerException

Guys, I think I found my way around it, I just need help with this detail.. what am I mising here?

[Chan Ag]

 

Kaspersky Ukshini wrote:

Kaspersky Ukshini wrote:

And NO LUCK! I'm getting this error when trying it: Exception in thread "main" java.lang.NullPointerException

Guys, I think I found my way around it, I just need help with this detail.. what am I mising here?

Sorry, I was just going on and on.

If you scroll up, you will see the following response by Jelle Klap.

Ater you declare and initialize the index array at line 6 it contains only null references.
You then dereference null inside your for-loop by invoking setValue() which results in a NullPointerException.

Specifically index[0] is null. When you type the following,

Pair[] index=new Pair[a.length];

you are only assigning index to an object that has several null references. In simple words, at this stage, Pair[0], Pair[1], Pair[arrayLength-1] etc are all null.

So if you try to access index[0] without assigning it a Pair, you will get a NullPointerException. When you type

index[i].setValue(a[i]);

what you are doing is

1. Get index[i], say index[0] value.
2. On the object you get at index[0], invoke the setValue method with the argument a[i].

So 1 gives you a null. And at 2, you get a NullPointerException.

But if you had done this...

Pair somePair = new Pair(.....);
index[i] = somePair;
index[i].setValue(a[i]);

you wouldn't get a NullPointerException.

[Kaspersky Ukshini]

But I'm doing it intentionaly, cause the Value variable holds he value, and I copy it by doing a[i], but the other value saves the INDEX of that value in the array, hence (i)

[Chan Ag]

setValue and setIndex are instance methods. Instance methods are invoked on objects as follows.

obj.instaceMethod(method arguments);

Here obj has to be an object.

null is not an object. You cannot invoke an instance method on null.

String a = null;
a.length(); 

If you execute the above code, you will get a NullPointerException cause you are trying to invoke an instance method on null.

String a = new String("Hello"); // String a = "Hello"; is better but let's ignore that for now.
a.length(); 

If you execute the above code, you will not get a NullPointerException cause you are invoking an instance method on an object.

In your code example, I get it that you need to invoke the setValue and setIndex methods. But your index(i) is null.
Now do you see where the problem is?

[Chan Ag]

 

Piet Souris wrote:
{ {2} }
{ {8,2} , {2} , {8}}
{ {8,2}, {4, 2}, {2} , {8} , {4} }

And so the longest subsequence is either {8, 2} or {4, 2}
The only worry is that the number of LinkedLists is increasing at
an alarming rate, about 2^n, which is deadly for any algorithm.
Guess I'll have to do some extra study...

Wow, Piet. Your program is cool. It works in all the cases. I could try it only today.

About the number of subsequences growing at an alarming rate, I have added one small refinement to your code. The idea is that we don't require the subsequence {8} in the second step cause we already have {8,2}. That is only step 1 of the refinement.
More refinements in this line are possible ( like you don't need to add the number to all the matching cases ) but I guess trickier ( for me because of the lack of the peace of mind because of the things going on in my lil space )

So just added this one step...

for (LinkedList<Integer> ll: subsequences) {
if (ints[index] >= ll.getFirst()) {
LinkedList<Integer> newlist = new LinkedList<>(ll);
newlist.addFirst(ints[index]);
newSubs.add(newlist);
}
}
if (newSubs.isEmpty()) { //added this check
LinkedList<Integer> temp = new LinkedList<>();
temp.add(ints[index]);
newSubs.add(temp);
}

I am still working on various other suggestions by Winston and others and my own proposed solution. I might just take a little time in getting back though.

Thanks.
Edit : Changed the code.

[Piet Souris]

hi Chan,

thanks for this enormous work!

Indeed, I realised that I was storing way too many sublists, but since OP never reacted,
I didn't spend any more time on it, well, not on this site.

I showed this problem to a collegue of mine, who got interested and is having a look
at it now. Having just done the algorithmic course at Coursera, the next interesting
question is: what is the asymptotic behaviour of this algortihm, given the improvements
that you mention.

Running the program on an array of 50 random elements, run time and number of
sublists tend to vary, but it looks more like an O(n^3) thing than the dreaded O(2^n).

To be continued!

Greetz,
Piet

[Chan Ag]

Ok, so if anybody is still interested in this, here's an implementation of the algorithm I was talking about a few days back. I think it's asymptotic computational complexity is close to O(N log N) as we are only adding each node at one place only and we are examining only the applicable nodes.

package algorithms.demos.week1;
import java.util.Collection;
public class Node<T> {
private T data;
private Node<T> parent;
private int depth;
private boolean leaf;
private boolean root;
private Collection<Node<T>> children;
public Node(T data, Node<T> parent) {
this.data = data;
this.parent = parent;
this.updateDepth(parent);
this.root = parent==null ? true : false;
this.leaf = true;
}
private void updateDepth(Node<T> parent) {
this.depth = parent != null ? parent.getDepth() + 1 : 0 ;
}
public T getData() {
return data;
}
public int getDepth() {
return depth;
}
public Node<T> getParent() {
return parent;
}
public boolean isLeaf() {
return leaf;
}
public boolean isRoot() {
return root;
}
public Collection<Node<T>> getChildren() {
return children;
}
public void setParent(Node<T> parent) {
this.parent = parent;
this.updateDepth(parent);
}
public void setChildren(Collection<Node<T>> children) {
this.children = children;
}
public String toString() {
return data.toString();
}
}

package algorithms.demos.week1;
import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
import java.util.TreeSet;
public class SubSequenceGenerator {
public static void main(String[] args) {
int[] sequence = {10, 9, -3 , 5 , 12 , 3 , -4 ,
-6 , -10 , 8 , 0 };
//int[] sequence = { 9,9,9,9,9 };
//int[] sequence = {};
System.out.println(SubSequenceGenerator.
getTheLongestDecreasingSubsequence(sequence));
}
public static final List<Node<Integer>>
getTheLongestDecreasingSubsequence(final int[] sequence) {
LongestDecreasingSubSequenceHelper helper = new
LongestDecreasingSubSequenceHelper();
Node<Integer> root = new Node<>(Integer.MAX_VALUE, null);
helper.leafsWithMaxDepth.add(root);
for (Integer i : sequence) {
Node<Integer> parent = helper.findParent(i, root);
Node<Integer> current = new Node<>(i, parent);
helper.addNode(current, parent);
}
return helper.getTheLongestDecreseaingSubsequence();
}
private static final class LongestDecreasingSubSequenceHelper {
int maxDepth = 0;
List<Node<Integer>> leafsWithMaxDepth = new ArrayList<>();
private final Node<Integer> findParent(Integer i, Node<Integer> root) {
Deque<Node<Integer>> nodesToExamine = new ArrayDeque<>();
nodesToExamine.addFirst(root);
Node<Integer> currentParent = null;
while (!nodesToExamine.isEmpty()) {
Node<Integer> examined = nodesToExamine.removeFirst();
currentParent = currentParent == null ? examined :
examined.getDepth() > currentParent.getDepth() ?
examined : currentParent;
Collection<Node<Integer>> children = examined.getChildren();
if (children !=null && !children.isEmpty()) {
for (Node<Integer> child : children) {
if (child.getData() < i.intValue()) {
break;
}
nodesToExamine.addFirst(child);
}
}
}
return currentParent;
}
private final void addNode(Node<Integer> current,
Node<Integer> parent) {
Collection<Node<Integer>> children = parent.getChildren();
if (children == null) {
children = new TreeSet<Node<Integer>>(
(Node<Integer> n1, Node<Integer> n2) ->
n1.getData() > n2.getData() ? -1 :
n1.getData() == n2.getData() ? 0 : 1);
parent.setChildren(children);
}
children.add(current);
this.checkAndUpdateMaxDepth(current);
}
private final void checkAndUpdateMaxDepth(Node<Integer> current) {
if (maxDepth < current.getDepth()) {
maxDepth = current.getDepth();
leafsWithMaxDepth.removeAll(leafsWithMaxDepth);
leafsWithMaxDepth.add(current);
}
if (maxDepth == current.getDepth()) {
leafsWithMaxDepth.add(current);
}
}
private final List<Node<Integer>>
getTheLongestDecreseaingSubsequence() {
LinkedList<Node><Integer>> sequence = new LinkedList<>();
Node<Integer> current = leafsWithMaxDepth.get(0);
while (current.getParent() != null ) {
sequence.addFirst(current);
current = current.getParent();
}
return sequence;
}
}
}

Until someone finds a sequence that it will fail for.. :-)

[Chan Ag]

 

Chan Ag wrote: I think it's asymptotic computational complexity is close to O(N log N) as we are only adding each node at one place only and we are examining only the applicable nodes.

No, it's O(N^2 log N).

Edit --

I think the nested class should really be a method local class inside the static method.

this.root = parent==null ? true : false; 

The above is too noisy. It should really be

 this.root = parent==null;

The following

if (child.getData() < i.intValue()) { 

could actually be this or similar ( if you add the null check ) --

if (child.getData().intValue() < i.intValue()) { 

or better so since we have the unboxed value of i already, it's no point first boxing it and then un-boxing it again. That parenthesis at the end has one more extra space which is inconsistent with the rest of the formatting.
The indentations created after breaking up long lines into shorter lines could also be made consistent.