Height of a Binary Search Tree

Problem Given a Binary Search Tree, compute its height — the length of the longest path from the root down to a leaf.

Input / Output

• Input: root — pointer to the root node of a BST (may be null)
• Output: an integer height

Constraints

• 0 <= number of nodes <= 10^5
• The tree may be skewed (a linked list, depth O(n)) or balanced (depth O(log n))
• Agree the convention up front: height of a single node is either 1 (node count) or 0 (edge count); an empty tree is 0 or -1 correspondingly

Example

• Single root node → height 1 under the node-count convention
• Right-skewed tree 1 -> 2 -> 3 → height 3; a perfectly balanced tree with n nodes → height ~log2(n)
• Empty tree → 0