The median of the given AVL tree

A long time ago I found this question and asked about an algorithm here.

My code is also available on GitHub.


Given a self-balancing tree (AVL), code a method that returns the
median.


(Median: the numerical value separating the higher half of a data
sample from the lower half. Example: if the series is


\$2, 7, 4, 9, 1, 5, 8, 3, 6\$


then the median is \$5\$.)

Now I have a solution I'd like to submit. The solution guarantees \$O(\log n)\$ time (since AVL trees are balanced), \$O( \log n)\$ extra space for the stack, and O(n) extra space to the number of children of every node. See the method called traverseTreeToFind

The median of a sorted sequence is the element whose index is \$\frac{N}{2}\$ (the number of elements is odd) or \$\frac{a[\frac{N}{2}-1] + a[\frac{N}{2}]}{2.0}\$ (the number of elements is even). With an AVL tree we need to perform an in-order tree walk to find the median.

Let the left subtree has \$L\$ nodes, and the right subtree has \$R\$ nodes. The number of nodes in the is \$N = L + R + 1\$. There are a few possible cases:

• \$L == R\$. There is no reason to traverse the tree. The median is the key of the root element.

• \$L == N / 2\$ and \$N\$ is even. The median is the average of the root and its predecessor.

• \$L == N / 2 - 1\$ and \$N\$ is even. The median is the average of the root and its successor.

• The median is something that we need to find traversing the left of right subtree.

I traverse the left subtree staring with its last nodes and go in the opposite direction of what the regular in-order tree walk would be. Why? Because it's likely the median will be found at the end of the left subtree. Please let me know if I am wrong. Here is how I proved that I was right:

\$\frac{N}{2} > \frac{L}{2}\$ means that the median index \$\frac{N}{2}\$ is at the right half of the left subtree (\$> \frac{L}{2}\$)

```
package com.avl;

import java.util.Deque;
import java.util.LinkedList;

public class AvlTree

To me it seems that you are overkilling it. Compare to the following:

package com.avl;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class AvlTree {

    private Node root;
    private int size;

    public AvlTree(int... keys) {
        if (keys == null || keys.length == 0) {
            throw new IllegalArgumentException("Null or empty array");
        }

        insert(keys);
    }

    /**
     * Computes the amount of child nodes in the left subtree of {@code node}.
     * Runs in constant time.
     * 
     * @param  node the node whose left subtree size to compute.
     * @return the amount of child nodes in the left subtree.
     */
    private int getLeftSubtreeSize(Node node) {
        int tmp = node.childCount;

        if (node.right != null) {
            tmp -= (node.right.childCount + 1);
        }

        return tmp;
    }

    /**
     * Returns the value of {@code index}th (in order) entry. Runs in 
     * logarithmic time.
     * 
     * @param root  the root of the tree.
     * @param index the index of the entry whose value to get.
     * @return the value of {@code index}th value.
     */
    private Node getNode(Node root, int index) {
        Node current = root;

        for (;;) {
            int leftSubtreeSize = getLeftSubtreeSize(current);

            if (index == leftSubtreeSize) {
                return current;
            }

            if (index > leftSubtreeSize) {
                index -= (leftSubtreeSize + 1);
                current = current.right;
            } else {
                current = current.left;
            }
        }
    }

    /**
     * Computes the median of this tree. Makes at most two calls to logarithmic 
     * time methods.
     * 
     * @return the median of this tree.
     */
    public double getMedian() {
        if (size == 0) {
            throw new IllegalStateException(
                    "Asking for median from an empty tree.");
        }

        if (size % 2 == 0) {
            int b = getNode(root, size / 2 - 1).key;
            int a = getNode(root, size / 2).key;
            return 0.5 * (a + b);
        } else {
            return getNode(root, size / 2).key;
        }
    }

    private Node insert(Node parent, int key) {
        if (parent == null) {
            ++size;
            return new Node(key);
        }

        if (key  0) {
                p.left = rotateLeft(p.left);
            }
            return rotateRight(p);
        }
        return p;
    }

    private Node rotateRight(Node p) {
        Node q = p.left;
        p.left = q.right;
        q.right = p;
        fixHeightAndChildCount(p);
        fixHeightAndChildCount(q);
        return q;
    }

    private Node rotateLeft(Node q) {
        Node p = q.right;
        q.right = p.left;
        p.left = q;
        fixHeightAndChildCount(q);
        fixHeightAndChildCount(p);
        return p;
    }

    private int height(Node p) {
        return p == null ? 0 : p.height;
    }

    private int bfactor(Node p) {
        return height(p.right) - height(p.left);
    }

    private void fixHeightAndChildCount(Node p) {
        int hl = height(p.left);
        int hr = height(p.right);
        p.height = (hl > hr ? hl : hr) + 1;
        p.childCount = 0;
        if (p.left != null) {
            p.childCount = p.left.childCount + 1;
        }
        if (p.right != null) {
            p.childCount += p.right.childCount + 1;
        }
    }

    public void insert(int... keys) {
        for (int key : keys) {
            root = insert(root, key);
        }
    }

    private static final class Node {

        private Node left;
        private Node right;
        private final int key;
        private int height;
        private int childCount;

        private Node(int value) {
            key = value;
            height = 1;
        }

        @Override
        public String toString() {
            return Integer.toString(key);
        }
    }

    public static void main(String[] args) {
        Deque list = new LinkedList<>();
        Deque arra = new ArrayDeque<>();
        int n = 2000000;

        long ta = System.currentTimeMillis();
        for (int i = 0; i < n; ++i) {
            list.addFirst(i);
        }
        long tb = System.currentTimeMillis();

        System.out.println("LinkedList: " + (tb - ta));

        ta = System.currentTimeMillis();
        for (int i = 0; i < n; ++i) {
            arra.addFirst(i);
        }
        tb = System.currentTimeMillis();

        System.out.println("ArrayDeque: " + (tb - ta));
    }
}

Summa summarum, you can optimize a bit if you cache in each node only the size of the left subtree. Also, when appending (addLast), say 2000000 elements, to ArrayDeque vs. LinkedList, the first one takes around 50 times less time than the LinkedList. Same applies to addFirst. (Try it.)

StackExchange Code Review Q#104525, answer score: 4