BST
Binary Search Tree

Concept:

In Binary Search Tree,

  • When we do the In-Order traversal, nodes will be visited in ascending order.
    In-Order Traversal
    For each Node,

    • Traverse the left subtree
    • Visit the node
    • Traverse the right subtree

    i.e. for above BST, nodes will be visited in following order,
    1 , 3 , 4 , 5 , 8 , 10 , 11

  • When we do the Reverse-In-Order traversal, nodes will be visited in descending order.
    Reverse-In-Order Traversal
    For each Node,

    • Traverse the right subtree
    • Visit the node
    • Traverse the left subtree

    i.e. for above BST, nodes will be visited in following order,
    11 , 10 , 8, 5 , 4 , 3 , 1

In both the above scenarios while visiting each node we just need to update the count of visited nodes. When count equals the n then it means that current node is the required one.


Code:

We have designed a class to return the Nth Largest and Smallest Node in BST using above concept.

Usage Details

Thanks.

Click Here to Subscribe for more Articles / Tutorials like this.