Question

Write a Java Program to find the largest value in each level of a Binary Search Tree.

Answer 1

Use level order traversal with a queue in Java to find the largest value in each level of a Binary Search Tree. Iterate over each level, compare node values to find the maximum, and print it out.

Step-by-step explanation:

To find the largest value in each level of a Binary Search Tree (BST) in Java, one approach is to use level order traversal. This can be achieved by using a queue to traverse the tree level by level and compare the node values to find the largest one at each level.

Example Java Program

Here's an example Java program for finding the largest values in each level of a BST:

import java.util.*;

class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
left = right = null;
}
}

public class BSTLargestInLevel {
Node root;

// Constructor
public BSTLargestInLevel() { root = null; }

// Function to find largest values
void findLargestInEachLevel(Node node) {
if (node == null)
return;

Queue queue = new LinkedList<>();
queue.add(node);

while (!queue.isEmpty()) {
int size = queue.size();
int max = Integer.MIN_VALUE;

while (size-- > 0) {
Node temp = queue.poll();
max = Math.max(max, temp.data);

// Insert the children of current node to the queue
if (temp.left != null) queue.add(temp.left);
if (temp.right != null) queue.add(temp.right);
}

System.out.println("Largest value in level: " + max);
}
}

public static void main(String[] args) {
BSTLargestInLevel tree = new BSTLargestInLevel();
// Assume BST is created and populated

// Find and print the largest values in each level
tree.findLargestInEachLevel(tree.root);
}
}

This program demonstrates how to iterate over each level of the tree and find the maximum value at each level, then print it out. You'll need to populate the BST with your own values before running this code.

Answer 2

To find the largest value in each level of a Binary Search Tree (BST) in Java, perform a level-order traversal using a queue, keeping track of the maximum value at each level and print it before proceeding to the next.

Step-by-step explanation:

Finding the Largest Value in Each Level of a Binary Search Tree

To find the largest value in each level of a binary search tree (BST) in Java, we need to perform a level-order traversal of the tree. This can be achieved using a queue data structure to traverse the tree in a breadth-first manner. During the traversal, we track the maximum value at each level and print it before moving to the next level. Here's a simple program that demonstrates this approach:

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
left = null;
right = null;
}
}

public class Main {
public static void findLargestValues(TreeNode root) {
if (root == null) {
return;
}

Queue queue = new LinkedList<>();
queue.offer(root);

while (!queue.isEmpty()) {
int levelSize = queue.size();
int levelMax = Integer.MIN_VALUE;
for (int i = 0; i < levelSize; i++) {
TreeNode currentNode = queue.poll();
if (currentNode.val > levelMax) {
levelMax = currentNode.val;
}

if (currentNode.left != null) {
queue.offer(currentNode.left);
}
if (currentNode.right != null) {
queue.offer(currentNode.right);
}
}
System.out.println("Largest value at current level: " + levelMax);
}
}

public static void main(String[] args) {
TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);
root.right.right = new TreeNode(18);
findLargestValues(root);

The class TreeNode represents a node in the BST. The findLargestValues function performs a level-order traversal and finds the largest value at each level. Note that in a BST, the largest value in each level is not necessarily the right-most node due to the tree's structure. This program will output the largest values for each level of the BST.