CODEWITHSUNDEEP
cdata-structuresbinary-search-tree
Mrunal Deole
Mrunal Deole

Reputation: 67

Leaf nodes from Preorder of a Binary Search Tree

Given a Preorder traversal of a Binary Search Tree. The task is to print leaf nodes of the Binary Search Tree from the given preorder.

Example:

Input : 67 34 12 45 38 60 80 78 79 95 100

Output: 12 38 60 79 100

Following is the recursive solution I came up with but not getting the correct output

Can anyone help me understand what I am doing wrong?

#include<stdio.h>
#define MAX 100

int preorder[MAX], n;

void leaf(int low,int high)         // prints leaf nodes from preorder
{
    if(high <= low)                 // base condition: print the leaf and return
    {
        printf("%d ", preorder[low]);
        return;
    }
   int root = preorder[low];                        //stores the value  of root node;
   int left =root > preorder[low+1]? low+1: low ;   // stores the index of left node, if left subtree ie empty sets left = low
   int right = low;                                 //stores the index of right node. Initialized to low

   for(int i = low; i<=high; i++)                   //finds the right node. i.e. first node larger than root(between low and high)
   {
       if(root < preorder[i]);
       {
           right = i;                               // stores the index of right node
           break;
       }       
   }
    
    if(left != low)                 //if left = low, then left subtree is empty
        leaf(left, right-1);        //recurse on the left subtree
    if(right != low)                //if right = low, then right subtree is empty
        leaf(right,high);           //recurse on the right subtree

}

int main()
{  
    printf("Enter size of input: ");
    scanf("%d",&n);
    printf("Enter input:");

    for(int i = 0; i<n; i++)
    {
        scanf("%d",&preorder[i]);
    }  

    leaf(0,n-1);
}

Upvotes: 0

Views: 195

Answers (1)

ryyker
ryyker

Reputation: 23236

Typo is here:

 for(int i = low; i<=high; i++) //finds the right node. ...
   {
       if(root < preorder[i]);//<-----  
                             ^
       ...

Causing the following lines to be executed regarless:

   right = i;                               // stores the index of right node
   break;

Upvotes: 1

Related Questions