Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Nth Highest Number in Binary Search Tree

Explore techniques to find the nth highest node in a binary search tree. Understand reverse in-order traversal and how using stored subtree counts optimizes the search. This lesson covers time and space complexities for balanced and degenerate trees.

We'll cover the following...

Statement

Given the root of a binary search tree and an integer value n, find the node with the nth^{th} highest value.

Example

Consider the following BST as an example:

G root 100 node1 50 root->node1 node2 200 root->node2 node3 25 node1->node3 node4 75 node1->node4 node5 125 node2->node5 node6 350 node2->node6

In this BST:

  • The highest node is 350.

  • The 2nd2^{nd} highest node is 200.

  • The 3rd3^{rd} highest node is 125.

  • The 4th4^{th} highest node is 100.

    And so on!

...