Question

Algorithms and Data Structures

Let T be a binary search tree which implements a dictionary. Let v be a node of T, and T_v be the subtree rooted at v. Design a recursive algorithm CountLE(v, k) which, given an input node v and a key k, returns the number of entries in T_v with key at most k.

Answer 1

creating binary search tree and we can generate post order ,pre order,in order.In this program iam using random function for generation of numbers.

import java.util.Random;
class TreeNode
{
TreeNode leftNode;
int data;
TreeNode rightNode;
public TreeNode(int nodeData)
{
data=nodeData;
leftNode=rightNode=null;
}
public void insert(int insertValue)
{
if(insertValue<data)
{
if(leftNode==null)
leftNode=new TreeNode(insertValue);
else
leftNode.insert(insertValue);
}
else if(insertValue>data)
{
if(rightNode==null)
rightNode=new TreeNode(insertValue);
else
rightNode.insert(insertValue);
}
}
}
class Tree
{
private TreeNode root;
public Tree()
{
root=null;
}
public void insertNode(int insertValue)
{
if(root==null)
root=new TreeNode(insertValue);
else
root.insert(insertValue);
}
public void preorderTraversal()
{
preorderHelper(root);
}
private void preorderHelper(TreeNode node)
{
if(node==null)
return;
System.out.printf("%d",node.data);
preorderHelper(node.leftNode);
preorderHelper(node.rightNode);
}
public void inorderTraversal()
{
inorderHelper(root);
}
private void inorderHelper(TreeNode node)
{
if(node==null)
return;
inorderHelper(node.leftNode);
System.out.printf("%d",node.data);
inorderHelper(node.rightNode);
}
public void postorderTraversal()
{
postorderHelper(root);
}
private void postorderHelper(TreeNode node)
{
if(node==null)
return;
postorderHelper(node.leftNode);
postorderHelper(node.rightNode);
System.out.printf("%d",node.data);
}
}
public class TreeTraverse
{
public static void main(String args[])
{
Tree tree=new Tree();
int value;
Random randomNumber=new Random();
System.out.println("Inserting the following values:");
for(int i=1;i<=10;i++)
{
value=randomNumber.nextInt(100);
System.out.print(value+" ");
tree.insertNode(value);
}
System.out.println("\n\nPerorder traversal");
tree.preorderTraversal();
System.out.println("\n\nInorder traversal");
tree.inorderTraversal();
System.out.println("\n\npostorder traversal");
tree.postorderTraversal();
System.out.println();
}
}

// This method is used for counting the nodes in binary search tree

int count(struct tnode *p)

{

        if( p == NULL)

                return(0);

        else

                if( p->lchild == NULL && p->rchild == NULL)

                        return(1);

                else

                        return(1 + (count(p->lchild) + count(p->rchild)));

}