Is this algorithm O(d), where d is the depth of the binary search tree

Question

I am practicing for a data structures exam and have been working on the question: "Write an algorithm that finds the kth highest node value in a binary search tree T. The algorithm must run in O(d), where d is the depth of the tree."

I have come up with this (after several hours) and am unsure about the runtime, I have traversed the tree twice, is this 2d and therefor just d? I was also hoping on some advice about how to reduce the number of methods I've used (if possible).

Here's my answer using a recursive helper method for counting the number of nodes in the tree and an in-order DFS:

public int getKthHighestValue(Node root, int k) {
    int nodeCount = countNodes(root);
    if (k < 0 || k > nodeCount)
        return -1;
    ArrayList<Integer> nodeList = new ArrayList<>();
    getNodeValues(root, nodeList);
    return nodeList.get(k-1);
}

private void getNodeValues(Node root, ArrayList<Integer> nodeList) {
    if (root == null) {
        return;
    }
    getNodeValues(root.getLeft(), nodeList);
    nodeList.add(root.getValue());
    getNodeValues(root.getRight(), nodeList);
}


private int countNodes(Node root) {
    if (root == null) {
        return 0;
    }
    return 1 + countNodes(root.getLeft()) + countNodes(root.getRight());
}

o(2d) and o(d) are equivalent. The factor 2 has no incidence on the evolution of d, o() complexity is to measure the growing of the time, not the time itself. (And it is stange to measure the height of the tree instead of it's size, but that's another story) — pdem, Jun 11 '19 at 15:28
Possible duplicate of [Find kth smallest element in a binary search tree in Optimum way](https://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way) — , Jun 11 '19 at 16:51

ggorlen · Accepted Answer · 2019-06-11T17:05:20.587

You're confusing two entirely different variables n and d. d is the depth of the tree and n is the number of nodes. The complexity for your algorithm is O(n) because it grows at a rate relative to the number of nodes in the tree and has no relationship to the depth of the tree. In a degenerate tree that only has left children (a linked list), your complexity is still the same.

Speaking generally, an O(d) algorithm entails use of a comparative recursive step that asks questions about the current node's value and traverses accordingly (a binary search). In this manner, you can move straight down the tree (relative to d) using the sorted property of the BST.

This is also why it's important to keep BSTs balanced (AVL/red-black tree, etc). Without balance, d is no longer meaningful and the complexity for insertions/removals/lookups starts to look like n instead of the desired O(n log(n)), which is the typical complexity for algorithms that cut the search space in half on every iteration.

Having said this, it's not clear that an O(d) algorithm is feasible without keeping additional information in each node using an order statistic tree (see this answer for details).

Yes n is the size of the tree and the purpose of the binary tree is to be accessed in o (ln(n) ) in this case so o(d) since d=log(n) base 2 — pdem, Jun 11 '19 at 15:33
Thanks this is very useful feedback. I am working on a new solution now — PumpkinBreath, Jun 11 '19 at 15:34

Is this algorithm O(d), where d is the depth of the binary search tree

1 Answers1