Coderust: Hacking the Coding Interview/

...

/

Nth Highest Number in Binary Search Tree

Nth Highest Number in Binary Search Tree

Given a binary search tree and an integer n, return node with the nth highest value.

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!

...