Analysis
Given your definition of a binary-tree we have the following,
Each Node have a Parent, L-child, and R-child .. where:
L < N
R > N
P > N
We also can do this:
L < N AND R > N => L < N < R => L < R
L < N AND P > N => L < N < P => L < P
R > N AND P > N => N < MIN(P,R)
N < MIN(P,R) AND L < N => L < N < MIN(P,R)
And now let's try expanding it, N.L = Left-child of N
:
N.L < N
N.R > N
N.P > N
N.L.L < N.L < MIN(N, N.L.R)
N.L.R > N.L > N.L.L
N.R.L < N.R < MIN(N, N.R.R)
N.R.R > N.R > N.R.L
IF N IS N.P LEFT-CHILD: N < N.P < MIN(N.P.P, N.P.R)
IF N IS N.P RIGHT-CHILD: N > N.P.R
Proposed Solution
This problem seems complex, but my solution will be using merge sort after inserting values in a traversal order Left-Right-Parent which will help the merge sort to get a time complexity somewhere between its average and optimal case, but with a small trick using the comparisons I've done above.
First we collect tree nodes in a list, using Left-Right-Parent traversal, given the fact that: N.L < N < MIN(N.R, N.P)
and with giving the parent a higher weight assuming O(N.R) <= O(N.P)
with values decrease linearly when we go left-side each time .. > N.R.R > N.R > N > N.L > N.L.L > ..
.
After collecting the tree nodes in that traversal order, the list have some sorted chunks, which will help the merge sort that we'll use next.
This solution works in: Time = O(n log n + n)
, Space = O(n)
Here is the algorithm written in Java (not tested):
private class Node Comparable<Node>
{
public Node R;
public Node L;
public int value;
public Node (Node L, int val, Node R)
{
this.L = L;
this.value = val;
this.R = R;
}
@Override
public int compareTo(Node other)
{
return ((other != null) ? (this.value-other.value) : 0);
}
}
class Main
{
private static Node head;
private static void recursive_collect (Node n, ArrayList<Node> list)
{
if (n == null) return;
if (n.left != null) recursive_collect (n.L, list);
if (n.right != null) recursive_collect (n.R, list);
list.add(n.value);
}
public static ArrayList<Node> collect ()
{
ArrayList<Node> list = new ArrayList<Node>();
recursive_collect (head, list);
return list;
}
// sorting the tree: O(n log n + n)
public static ArrayList<Node> sortTree ()
{
// Collecting nodes: O(n)
ArrayList<Node> list = collect();
// Merge Sort: O(n log n)
Collections.sort(list);
return list;
}
// The example in the picture you provided
public static void createTestTree ()
{
Node left1 = new Node (new Node(null,-2,null), -1, new Node(null,0,null));
Node left2 = new Node (new Node(null,-1,null), 0, new Node(null,1,null));
Node right = new Node (left2, 1, new Node(null,2,null));
head = new Node (left1, 0, right);
}
// test
public static void main(String [] args)
{
createTestTree ();
ArrayList<Node> list = sortTree ();
for (Node n : list)
{
System.out.println(n.value);
}
}
}