Leaf nodes from Preorder of BST Java

PROGRAM TO FIND LEAF NODES FROM PREORDER OF A BST



import java.util.*;
class MAIN {
  
// Print the leaf node from the given preorder of BST. 
static void leafNode(int preorder[], int n) 
{ 
    Stack<Integer> s = new Stack<Integer> (); 
    for (int i = 0, j = 1; j < n; i++, j++) 
    { 
        boolean found = false; 
  
        if (preorder[i] > preorder[j]) 
            s.push(preorder[i]); 
  
        else
        { 
            while (!s.isEmpty()) 
            { 
                if (preorder[j] > s.peek()) 
                { 
                    s.pop(); 
                    found = true; 
                } 
                else
                    break; 
            } 
        } 
  
        if (found) 
            System.out.print(preorder[i] + " "); 
    } 
  
    // Since rightmost element is always leaf node. 
    System.out.println(preorder[n - 1]); 
} 
  
// Driver code 
public static void main(String[] args) 
{ 
    int preorder[] = { 890, 325, 290, 530, 965 }; 
    int n = preorder.length; 
  
    leafNode(preorder, n); 
} 
} 


OUTPUT:
290 530 965

Comments

Post a Comment

Popular posts from this blog

Find first non-repeating character Python

PROGRAM TO FIND FIRST NON-REPEATING CHARACTER IN A STRING IN ONE TRAVERSAL NO_OF_CHARS = 256     # Returns an array of size 256 containg count # of characters in the passed char array def getCharCountArray(string):      count = [ 0 ] * NO_OF_CHARS      for i in string:          count[ ord (i)] + = 1      return count     # The function returns index of first non-repeating # character in a string. If all characters are repeating # then returns -1 def firstNonRepeating(string):      count = getCharCountArray(string)      index = - 1      k = 0          for i in string:          if count[ ord (i)] = = 1 :              index = k       ...
Read more

Find Duplicates Java

PROGRAM TO FIND REPEATING NUMBERS IN AN ARRAY class MAIN {           public static void main(String args[]) {          int numRay[] = { 0 , 4 , 3 , 2 , 7 , 8 , 2 , 3 , 1 };               for ( int i = 0 ; i < numRay.length; i++) {              numRay[numRay[i] %  numRay.length] = numRay[numRay[i] %  numRay.length] + numRay.length;          }          System.out.println( "The repeating elements are : " );          for ( int i = 0 ; i < numRay.length; i++) {              if (numRay[i] >= numRay.length* 2 ) {                ...
Read more

Brackets in Matrix Chain Multiplication Java

PROGRAM TO MULTIPLY MATRICES EFFICIENTLY import java.io.*; import java.util.*; class GFG {      static int [][] dp = new int [ 100 ][ 100 ];      // Function for matrix chain multiplication    static int matrixChainMemoised( int [] p, int i, int j)    {      if (i == j)       {        return 0 ;      }      if (dp[i][j] != - 1 )       {        return dp[i][j];      }      dp[i][j] = Integer.MAX_VALUE;      for ( int k = i; k < j; k++)       {        dp[i][j] = Math.min(          dp[i][j], matrixChainMemoised(p, i, k)          + matrixChainMemoised(p, k + 1 , j) ...
Read more