How to find Second largest element in BST ?



How to find Second largest element in BST ?

  • In an N-ary tree, the second largest value in the given tree to find and return the node. Return NULL if no node with required value is present.
  • For example, in the given tree
Second largest element in a BST

Second largest element in a BST

    Second largest node is 20.

  • A simple solution is to traverse the array twice. In the first traversal the maximum value node to be find.
  • In the second traversal find the greatest element node less than the element obtained in first traversal.
  • This solution O(n) is the time complexity.
  • To find the second largest element in a single traversal to be efficient solution.

Algorithm

    Initialize two nodes first and second to NULL as,
      first = second = NULL
    Start traversing the tree,
      If the current node data say root->key is greater than first->key then update first and second as, second = first first = root If the current node data is in between first and second, then update second to store the value of current node as second = root
    Return the node stored in second.

Sample Code in Java

// Java code to find second largest element in BST 
  
// A binary tree node 
class Node { 
  
    int data; 
    Node left, right; 
  
    Node(int d) 
    { 
        data = d; 
        left = right = null; 
    } 
} 
  
class BinarySearchTree { 
  
    // Root of BST 
    Node root; 
  
    // Constructor 
    BinarySearchTree() 
    { 
        root = null; 
    } 
  
    // function to insert new nodes 
    public void insert(int data) 
    { 
        this.root = this.insertRec(this.root, data); 
    } 
      
    /* A utility function to insert a new node with given  
    key in BST */
    Node insertRec(Node node, int data) 
    { 
        /* If the tree is empty, return a new node */
        if (node == null) { 
            this.root = new Node(data); 
            return this.root; 
        } 
  
        /* Otherwise, recur down the tree */
        if (data < node.data) { 
            node.left = this.insertRec(node.left, data); 
        } else { 
            node.right = this.insertRec(node.right, data); 
        } 
        return node; 
    } 
  
    // class that stores the value of count 
    public class count { 
        int c = 0; 
    } 
  
    // Function to find 2nd largest element 
    void secondLargestUtil(Node node, count C) 
    {    
        // Base cases, the second condition is important to 
        // avoid unnecessary recursive calls 
        if (node == null || C.c >= 2) 
            return; 
              
        // Follow reverse inorder traversal so that the 
        // largest element is visited first 
        this.secondLargestUtil(node.right, C);  
          
         // Increment count of visited nodes 
        C.c++; 
          
        // If c becomes k now, then this is the 2nd largest 
        if (C.c == 2) { 
            System.out.print("2nd largest element is "+ 
                                              node.data); 
            return; 
        } 
          
         // Recur for left subtree 
        this.secondLargestUtil(node.left, C);  
    } 
  
    // Function to find 2nd largest element 
    void secondLargest(Node node) 
    {    
        // object of class count 
        count C = new count();  
        this.secondLargestUtil(this.root, C); 
    } 
  
    // Driver function 
    public static void main(String[] args) 
    { 
        BinarySearchTree tree = new BinarySearchTree(); 
          
        /* Let us create following BST 
              50 
           /     \ 
          30      70 
         /  \    /  \ 
       20   40  60   80 */
         
        tree.insert(50); 
        tree.insert(30); 
        tree.insert(20); 
        tree.insert(40); 
        tree.insert(70); 
        tree.insert(60); 
        tree.insert(80); 
  
        tree.secondLargest(tree.root); 
    } 
} 

Output

2nd largest element is 70

Time Complexity

  • Time Complexity: The above solution is O(h) where h is height of BST.


Related Searches to How to find Second largest element in BST ?