Scribd
Upload
6 views17 pages

Print Boundary of Binary Tree

The document contains multiple Java programs that implement various data structures and algorithms, including a binary tree for printing boundary nodes, a sliding window maximum algorithm, cycle detection in linked lists, segregation of even and odd nodes in linked lists, and a celebrity problem solution. Each program includes methods for inserting nodes, detecting cycles, and processing user input. The document demonstrates practical applications of data structures such as trees and linked lists in solving computational problems.

Uploaded by

gunjanbhartia2003
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views17 pages

Print Boundary of Binary Tree

The document contains multiple Java programs that implement various data structures and algorithms, including a binary tree for printing boundary nodes, a sliding window maximum algorithm, cycle detection in linked lists, segregation of even and odd nodes in linked lists, and a celebrity problem solution. Each program includes methods for inserting nodes, detecting cycles, and processing user input. The document demonstrates practical applications of data structures such as trees and linked lists in solving computational problems.

Uploaded by

gunjanbhartia2003
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

//Print Boundary

import [Link];

class Node {
int data;
Node left, right;

Node(int item) {
data = item;
left = right = null;
}
}

public class PrintBoundary {


static Node root;

// Function to insert a node into the binary tree


static Node insert(Node root, int data) {
if (root == null)
return new Node(data);
if ([Link] < data)
[Link] = insert([Link], data);
else
[Link] = insert([Link], data);
return root;
}

// Function to print the boundary nodes of a binary tree


static void printBoundary(Node node) {
if (node != null) {
[Link]([Link] + " ");
printBoundaryLeft([Link]);
printLeaves([Link]);
printLeaves([Link]);
printBoundaryRight([Link]);
}
}

// Function to print the left boundary nodes of a binary tree


static void printBoundaryLeft(Node node) {
if (node != null) {
if ([Link] != null) {
[Link]([Link] + " ");
printBoundaryLeft([Link]);
} else if ([Link] != null) {
[Link]([Link] + " ");
printBoundaryLeft([Link]);
}
}
}

// Function to print the right boundary nodes of a binary tree


static void printBoundaryRight(Node node) {
if (node != null) {
if ([Link] != null) {
printBoundaryRight([Link]);
[Link]([Link] + " ");
} else if ([Link] != null) {
printBoundaryRight([Link]);
[Link]([Link] + " ");
}
}
}

// Function to print the leaves of a binary tree


static void printLeaves(Node node) {
if (node != null) {
printLeaves([Link]);
if ([Link] == null && [Link] == null)
[Link]([Link] + " ");
printLeaves([Link]);
}
}

public static void main(String args[]) {


Scanner sc = new Scanner([Link]);
int input = [Link]();

while (input >= 0) {


root = insert(root, input);
input = [Link]();
}

printBoundary(root);
[Link]();
}
}

//Stack perm
import [Link].*;
public class Max_Sliding {
static void maximum(int arr[], int N, int K)
{
int j, max;
for (int i = 0; i <= N - K; i++) {
max = arr[i];
for (j = 1; j < K; j++) {
if (arr[i + j] > max)
max = arr[i + j];
}
[Link](max + " ");
}
}
public static void main(String args[])
{
Scanner sc=new Scanner([Link]);
int n=[Link]();
int arr[]=new int[n];
for(int i=0;i<n;i++)
{
arr[i]=[Link]();
}
int K = [Link]();
maximum(arr,n, K);
}
}

//max sliding
import [Link].*;
public class Max_Sliding {
static void maximum(int arr[], int N, int K)
{
int j, max;
for (int i = 0; i <= N - K; i++) {
max = arr[i];
for (j = 1; j < K; j++) {
if (arr[i + j] > max)
max = arr[i + j];
}
[Link](max + " ");
}
}
public static void main(String args[])
{
Scanner sc=new Scanner([Link]);
int n=[Link]();
int arr[]=new int[n];
for(int i=0;i<n;i++)
{
arr[i]=[Link]();
}
int K = [Link]();
maximum(arr,n, K);
}
}

//loop
import [Link];

class Node {
int data;
Node next;

public Node(int data) {


[Link] = data;
[Link] = null;
}
}

public class Loop {

static Node head;

// Function to insert a node at the beginning of the linked list


static void insert(int data) {
Node newNode = new Node(data);
[Link] = head;
head = newNode;
}

// Function to detect a cycle in a linked list using Floyd's Cycle-


Finding Algorithm
static boolean detectCycle() {
Node slow = head, fast = head;

while (fast != null && [Link] != null) {


slow = [Link];
fast = [Link];

// If there is a cycle, the pointers will meet at some


point
if (slow == fast) {
return true;
}
}
return false;
}

// Function to create a cycle in the linked list


static void createCycle(int a, int b) {
if (head == null || [Link] == null) {
[Link]("Error: Insufficient nodes in the linked
list to create a cycle.");
return;
}

Node p1 = head;
Node p2 = head;

// Move p1 to the 'a' position


for (int i = 0; i < a; i++) {
p1 = [Link];

// Check if 'a' is out of bounds


if (p1 == null) {
[Link]("Error: Position 'a' is out of
bounds.");
return;
}
}

// Move p2 to the 'b' position


for (int i = 0; i < b; i++) {
p2 = [Link];

// Check if 'b' is out of bounds


if (p2 == null) {
[Link]("Error: Position 'b' is out of
bounds.");
return;
}
}

// Create a cycle
[Link] = p1;
}

public static void main(String[] args) {


Scanner scanner = new Scanner([Link]);

[Link]("Enter the number of nodes in the linked


list:");
int n = [Link]();
[Link]("Enter the elements of the linked list:");

// Creating the linked list


for (int i = 0; i < n; i++) {
int data = [Link]();
insert(data);
}

[Link]("Enter the positions (a and b) to create a


cycle (0-based indexing):");
int a = [Link]();
int b = [Link]();

// Creating a cycle
createCycle(a, b);

// Detecting a cycle
if (detectCycle()) {
[Link]("Cycle detected in the linked list.");
} else {
[Link]("No cycle detected in the linked
list.");
}

[Link]();
}
}

//PQDLL
import [Link];

class Node {
int data;
Node next;

Node(int data) {
[Link] = data;
[Link] = null;
}
}

public class EvenOdd {


static Node head;

static void insert(int data) {


Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while ([Link] != null) {
temp = [Link];
}
[Link] = newNode;
}
}

static void segregateEvenOdd() {


if (head == null || [Link] == null) {
return; // No need to segregate if the list has 0 or 1 node
}

Node evenStart = null, evenEnd = null;


Node oddStart = null, oddEnd = null;

Node current = head;

while (current != null) {


int data = [Link];

if (data % 2 == 0) {
if (evenStart == null) {
evenStart = current;
evenEnd = evenStart;
} else {
[Link] = current;
evenEnd = [Link];
}
} else {
if (oddStart == null) {
oddStart = current;
oddEnd = oddStart;
} else {
[Link] = current;
oddEnd = [Link];
}
}

current = [Link];
}

if (evenStart == null || oddStart == null) {


return; // No need to segregate if there are no even or odd
nodes
}
[Link] = oddStart;
[Link] = null;

head = evenStart;
}

static void display() {


Node temp = head;
while (temp != null) {
[Link]([Link] + " ");
temp = [Link];
}
[Link]();
}

public static void main(String[] args) {


Scanner scanner = new Scanner([Link]);

[Link]("Enter the number of elements in the linked


list: ");
int n = [Link]();

[Link]("Enter the elements of the linked list:");


for (int i = 0; i < n; i++) {
int data = [Link]();
insert(data);
}

[Link]("Linked list before segregation:");


display();

segregateEvenOdd();

[Link]("Linked list after segregating even and odd


nodes:");
display();

[Link]();
}
}

//BiotonicDLL
import [Link];

class Node {
int data;
Node next;

public Node(int data) {


[Link] = data;
[Link] = null;
}
}

public class Loop {

static Node head;

// Function to insert a node at the beginning of the linked list


static void insert(int data) {
Node newNode = new Node(data);
[Link] = head;
head = newNode;
}

// Function to detect a cycle in a linked list using Floyd's Cycle-


Finding Algorithm
static boolean detectCycle() {
Node slow = head, fast = head;

while (fast != null && [Link] != null) {


slow = [Link];
fast = [Link];

// If there is a cycle, the pointers will meet at some


point
if (slow == fast) {
return true;
}
}
return false;
}

// Function to create a cycle in the linked list


static void createCycle(int a, int b) {
if (head == null || [Link] == null) {
[Link]("Error: Insufficient nodes in the linked
list to create a cycle.");
return;
}

Node p1 = head;
Node p2 = head;
// Move p1 to the 'a' position
for (int i = 0; i < a; i++) {
p1 = [Link];

// Check if 'a' is out of bounds


if (p1 == null) {
[Link]("Error: Position 'a' is out of
bounds.");
return;
}
}

// Move p2 to the 'b' position


for (int i = 0; i < b; i++) {
p2 = [Link];

// Check if 'b' is out of bounds


if (p2 == null) {
[Link]("Error: Position 'b' is out of
bounds.");
return;
}
}

// Create a cycle
[Link] = p1;
}

public static void main(String[] args) {


Scanner scanner = new Scanner([Link]);

[Link]("Enter the number of nodes in the linked


list:");
int n = [Link]();

[Link]("Enter the elements of the linked list:");

// Creating the linked list


for (int i = 0; i < n; i++) {
int data = [Link]();
insert(data);
}

[Link]("Enter the positions (a and b) to create a


cycle (0-based indexing):");
int a = [Link]();
int b = [Link]();
// Creating a cycle
createCycle(a, b);

// Detecting a cycle
if (detectCycle()) {
[Link]("Cycle detected in the linked list.");
} else {
[Link]("No cycle detected in the linked
list.");
}

[Link]();
}
}

//Even Odd
import [Link];

class Node {
int data;
Node next;

Node(int data) {
[Link] = data;
[Link] = null;
}
}

public class EvenOdd {


static Node head;

static void insert(int data) {


Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while ([Link] != null) {
temp = [Link];
}
[Link] = newNode;
}
}

static void segregateEvenOdd() {


if (head == null || [Link] == null) {
return; // No need to segregate if the list has 0 or 1 node
}

Node evenStart = null, evenEnd = null;


Node oddStart = null, oddEnd = null;

Node current = head;

while (current != null) {


int data = [Link];

if (data % 2 == 0) {
if (evenStart == null) {
evenStart = current;
evenEnd = evenStart;
} else {
[Link] = current;
evenEnd = [Link];
}
} else {
if (oddStart == null) {
oddStart = current;
oddEnd = oddStart;
} else {
[Link] = current;
oddEnd = [Link];
}
}

current = [Link];
}

if (evenStart == null || oddStart == null) {


return; // No need to segregate if there are no even or odd
nodes
}

[Link] = oddStart;
[Link] = null;

head = evenStart;
}

static void display() {


Node temp = head;
while (temp != null) {
[Link]([Link] + " ");
temp = [Link];
}
[Link]();
}

public static void main(String[] args) {


Scanner scanner = new Scanner([Link]);

[Link]("Enter the number of elements in the linked


list: ");
int n = [Link]();

[Link]("Enter the elements of the linked list:");


for (int i = 0; i < n; i++) {
int data = [Link]();
insert(data);
}

[Link]("Linked list before segregation:");


display();

segregateEvenOdd();

[Link]("Linked list after segregating even and odd


nodes:");
display();

[Link]();
}
}

//Celebrity Problem
import [Link];

public class CelebrityProblem {

static int findCelebrity(int[][] matrix, int n) {


int candidate = 0;

// Find a potential candidate


for (int i = 1; i < n; i++) {
if (knows(candidate, i, matrix)) {
candidate = i;
}
}

// Verify if the candidate is a celebrity


for (int i = 0; i < n; i++) {
if (i != candidate && (knows(candidate, i, matrix) || !
knows(i, candidate, matrix))) {
return -1; // No celebrity found
}
}

return candidate;
}

static boolean knows(int a, int b, int[][] matrix) {


return matrix[a][b] == 1;
}

public static void main(String[] args) {


Scanner scanner = new Scanner([Link]);

[Link]("Enter the number of people: ");


int n = [Link]();

// Create a matrix to represent who knows whom (1 means they


know, 0 means they don't)
int[][] matrix = new int[n][n];

[Link]("Enter the matrix elements (1 for knowing, 0


for not knowing):");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = [Link]();
}
}

int celebrity = findCelebrity(matrix, n);

if (celebrity != -1) {
[Link]("Celebrity found at index: " +
celebrity);
} else {
[Link]("No celebrity found.");
}

[Link]();
}
}

//Min Stack
import [Link];
import [Link];

class Mystack {
Stack<Integer> s;
Stack<Integer> a;

Mystack() {
s = new Stack<>();
a = new Stack<>();
}

void getMin() {
if ([Link]())
[Link]("Stack is Empty");
else
[Link]("Minimum element: " + [Link]());
}

void peek() {
if ([Link]()) {
[Link]("Stack is Empty");
return;
}
int t = [Link]();
[Link]("Top most element: " + t);
}

void pop() {
if ([Link]()) {
[Link]("Stack is Empty");
return;
} else {
int t = [Link]();
[Link]("Removed element: " + t);

if (t == [Link]())
[Link]();
}
}

public void push(int x) {


[Link](x);

if ([Link]() || x <= [Link]()) {


[Link](x);
}
}
}

public class MinStack {


public static void main(String args[]) {
Mystack s = new Mystack();
Scanner sc = new Scanner([Link]);

[Link]("Enter the number of elements: ");


int n = [Link]();

for (int i = 0; i < n; i++) {


[Link]("Enter element " + (i + 1) + ": ");
int m = [Link]();
[Link](m);
}

[Link]();
[Link]();
[Link]();
[Link]();
[Link](1);
[Link]();
[Link]();

}
}

//stockspan
import [Link];
import [Link];
import [Link];

public class Stockspan {


static void calculateStockSpan(int[] arr, int n, int[] S) {
Stack<Integer> stack = new Stack<>();
[Link](0);
S[0] = 1;

for (int i = 1; i < n; i++) {


while (![Link]() && arr[[Link]()] <= arr[i]) {
[Link]();
}
S[i] = [Link]() ? (i + 1) : (i - [Link]());
[Link](i);
}
}
static void printArray(int[] arr) {
[Link]([Link](arr));
}

public static void main(String[] args) {


Scanner scanner = new Scanner([Link]);

[Link]("Enter the number of days:");


int n = [Link]();
int[] arr = new int[n];

[Link]("Enter the stock prices for each day:");

for (int i = 0; i < n; i++) {


arr[i] = [Link]();
}

int[] stockSpans = new int[n];


calculateStockSpan(arr, n, stockSpans);

[Link]("Stock Span for each day:");


printArray(stockSpans);

[Link]();
}
}

You might also like