Time complexity of finding the diameter of a Binary Search Tree (BST)
Asked by Rahul_Mehta | Textbook Reference: Cormen (CLRS) Algorithms
What is the optimal time complexity to find the diameter of a Binary Search Tree if we are only given the root node?
A standard recursive approach takes $O(N^2)$ in the worst-case if the tree is highly skewed and we compute the height of the left and right subtrees repeatedly inside the recursion.
Can we optimize this to $O(N)$? If so, what is the design? Here is my recursive structure:
```cpp
int height(Node* root) {
if (!root) return 0;
return 1 + max(height(root->left), height(root->right));
}
int diameter(Node* root) {
if (!root) return 0;
int lh = height(root->left);
int rh = height(root->right);
return max({lh + rh, diameter(root->left), diameter(root->right)});
}
```
How can we do this in $O(N)$ time with minimal auxiliary space?
Community Explanations (2)
hello
Yes, we can definitely find the diameter of a BST (or any Binary Tree) in $O(N)$ time.
### The Problem with the $O(N^2)$ approach
In your code, you call `height()` inside `diameter()` for each node. Since `height()` itself takes $O(d)$ time where $d$ is the depth, in the worst-case (skewed tree), the height operations sum up to $O(N^2)$.
### The $O(N)$ Optimization
We can calculate the height and diameter in a **single post-order traversal**. Instead of returning only the diameter, each recursive call will return a pair containing:
1. **Height** of the current subtree.
2. **Diameter** of the current subtree.
Here is the clean implementation in C++:
```cpp
#include
#include
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
// Pair: {height, diameter}
pair diameterOptimized(Node* root) {
if (root == nullptr) {
return {0, 0}; // Height = 0, Diameter = 0
}
pair leftSub = diameterOptimized(root->left);
pair rightSub = diameterOptimized(root->right);
int currentHeight = 1 + max(leftSub.first, rightSub.first);
// Diameter can either pass through root or lie entirely in subtrees
int diameterThroughRoot = leftSub.first + rightSub.first;
int currentDiameter = max({diameterThroughRoot, leftSub.second, rightSub.second});
return {currentHeight, currentDiameter};
}
int getDiameter(Node* root) {
return diameterOptimized(root).second;
}
```
### Complexity:
- **Time Complexity:** $O(N)$ since we visit each node exactly once.
- **Auxiliary Space:** $O(H)$ where $H$ is the height of the tree (due to the recursive call stack). In the worst case, $H = N$ (skewed tree), and in the best case, $H = \log N$ (balanced tree).