CODEWITHSUNDEEP
algorithmrecursiontime-complexitybinary-search-tree
PumpkinBreath
PumpkinBreath

Reputation: 915

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

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());
}

Upvotes: 2

Views: 481

Answers (1)

ggorlen
ggorlen

Reputation: 56965

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).

Upvotes: 4

Related Questions