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.

Join LinkedIn Group of Python Professional Developers who wish to expand their network and share ideas.

You can also follow us On Twitter :

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