22. Write a recursive function member 1eve10 for class template BST that determi

Question

22. Write a recursive function member 1eve10 for class template BST that determines the level in the BST at which a specified item is located. The root of the BST is at level 0, its children are at levell, and so on.

24. The worst-case number of comparisons in searching a BST is equal to its height, that is, the number oflevels in the tree.Write a recursive function member hei ght 0 for class template BST to determine the height of the BST.

25. Write a recursive function member 1eafCountO for class template BST to count the leaves in a binary tree. (Hint: How is the number of leaves in the entire tree related to the number of leaves in the left and right subtrees of the root?)

Explanation / Answer

import java.util.*;
import java.io.*;

public class Node// Binary tree implementation
{
int val;// Value assign to node
Node left;// left pointer of node
Node right;// right of node
  
Node(int val_)
{
val = val_;
}
  
static int height(Node node)
{
if (node == null)
return -1;// not exist
int leftHeight = height(node.left);// find for left subtree
int rightHeight = height(node.right);// find for right subtree
return 1+Math.max(leftHeight, rightHeight);// deepest node in the tree
}
  
static int countleaves(Node root)
{
if (root == null)
return 0;
if (root.left == null && root.right == null)// both child must be null
return 1;
else
return countleaves(root.left)+countleaves(root.right);// add leaves of left and right subtree
}
  
static int level(Node node, int item)
{
return levelHelper(node , item, 0);// Level of root is 0
}
  
static int levelHelper(Node node, int item, int level)
{
if (node == null)
return 0;//
if (node.val == item)
return level;// Got item return level
int belowLevel = levelHelper(node.left, item, level+1);// Go to the down level increment level
if (belowLevel != 0)// left child is not null
return belowLevel;
belowLevel = levelHelper(node.right, item, level+1);// Go to the down level increment leve;
return belowLevel;
}
  
public static void main(String[] args)
{
Node root = new Node(3);
root.left = new Node(2);
root.right = new Node(4);
root.right.right = new Node(5);
  
System.out.println(level(root, 4));// print 1
System.out.println(level(root, 5));//print 2
  
System.out.println(height(root));// height is 2
System.out.println(countleaves(root));// 2 leaves(2, 5)
}
}

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.