Worst Case Binary Tree - Determine "Sorted-ness"

Question

In the worst case, creating a binary tree from a known list will be O(n²), but the average case is O(n logn). The difference between the worst case and the average case depends on how unbalanced the tree is after creation. If maxDepth == n, then this is the worst case and if maxDepth == log(n) then this is the best case. Knowing maxDepth before building the tree would give a lot of insight into the running time of creating the tree.

Max Depth

Is there a way to determine max-depth (or an approximation) in O(n) time? I could not think of a way to do this. Instead I opted to try and find the "sorted-ness" of the initial list.

Sorted-ness

In the worst case example of a binary tree, a sorted list will end up being functionally equivalent to a linked-list. The more sorted the list is, the worse the performance of the binary tree. I could not find anything that would give a "sort-factor" of a list. The algorithm I tried worked for what I needed, but it doesn't feel "right"*.

public double sortFactor(int[] ar) {
    //assume lists are larger than 10000 elements
    int prevSum = ar[0] + ar[1] + ar[2];
    int numIncreasing = 0;
    for(int i=3; i < ar.length-3; i+=3) {
        int sum = ar[i] + ar[i+1] + ar[2];
        if (sum > prevSum) {
            numIncreasing++;
        }
        prevSum = sum;
    }
    int totalSets = ar.length/3;
    double sortFactor = (double) numIncreasing / (double) totalSets;
    return sortFactor;
}

*"right" - This algorithm isn't based on any proof or concept that sits on solid ground. Its based on fuzzing the data to see if groups of 3 are in sorted to semi-sorted order. 3 was chosen because it is larger than both 1 and 2.

Questions

Is there a way to determine max-depth(or an approximation) of a future binary tree based on given list in O(n) time?

Is "sorted-ness" a determinable property of a list? Can it be determined in O(n) time or would this require a much larger time complexity space?

Disclaimer

I am aware of self-balancing binary trees (Red-Black, AVL), but for the purposes of this question they are uninteresting. They do not relate to either of the questions above, but rather solve the background information on where those two questions originated.

"Sortedness" of a list can be approximated as the number of swaps required to sort it and can be computed in O(nlogn). But there are other lists besides sorted lists that lead to the worst case height. Consider the list [10, 9, 8, 7, 6, 1, 2, 3, 4 ,5] for example. What you need is a more generic measure of entropy. — kfx
How are you creating the binary tree in the first place? Your question doesn't make sense without this context. — comingstorm
@comingstorm, I should have specified binary search tree. Insertion is being done linearly from a given array. The given array is what I would like to perform operations on to determine its "sorted-ness" or what its max-depth would be, if it were converted into a BST. — Scott
@kfx: Out of curiosity, can you do that without actually sorting it? I can see it for the initial partition, but what then? — 500 - Internal Server Error
Nitpick: "binary tree" does not imply "binary search tree". It just means a tree where each node is limited to two children. There are plenty of binary tree-based data structures that don't maintain the BST invariant. — user2357112 supports Monica

David Eisenstat David Eisenstat · Accepted Answer · 2016-02-02T23:07:18

It certainly can be done in time O(n log n). I'm skeptical about O(n) in the linear decision tree model, but I don't have any evidence.

Keep a sorted map from the intervals between existing keys to the depth at which the new node would be inserted. For each point in order, find its interval and split into two at depth plus one.

Example execution on 3, 1, 4, 5, 9:

(-inf, inf): 0

insert 3

(-inf, 3): 1
(3, inf): 1

insert 1

(-inf, 1): 2
(1, 3): 2
(3, inf): 1

insert 4

(-inf, 1): 2
(1, 3): 2
(3, 4): 2
(4, inf): 2

insert 5

(-inf, 1): 2
(1, 3): 2
(3, 4): 2
(4, 5): 3
(5, inf): 3

insert 9

(-inf, 1): 2
(1, 3): 2
(3, 4): 2
(4, 5): 3
(5, 9): 4
(9, inf): 4

for an answer of depth 4 (including the null nodes). Here's the tree (* denotes null):

      3
     / \
    /   \
   /     \
  1       4
 / \     / \
*   *   *   5
           / \
          *   9
             / \
            *   *

Worst Case Binary Tree - Determine "Sorted-ness"

1 Answers