Scribd
Upload
2 views56 pages

IDSA Module3 ProgramMaterial

Uploaded by

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

IDSA Module3 ProgramMaterial

Uploaded by

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

Binary Tree

​ Inclass

1) import [Link].*;

class Node

​ int data;

​ Node left;

​ Node right;

​ public Node(int d)

​ {

​ data = d;

​ }

class Binarytree

​ public Node insert(int arr[],int n)

​ {

Queue<Node> q = new LinkedList<>();


​ Node root = new Node(arr[0]);

​ [Link](root);

​ int i = 1;

while(![Link]() && i<n)

​ {

​ Node curr = [Link]();

​ [Link] = new Node(arr[i]);

[Link]([Link]);

​ i++;

​ if(i<n)

​{

[Link] = new Node(arr[i]);

[Link]([Link]);

​}

​ i++;

​ }

​ return root;

​ }

​ public void BFS(Node root)


​ {

Queue<Node> q = new LinkedList<>();

​ [Link](root);

while(![Link]())

​ {

​ Node curr = [Link]();

[Link]([Link]+" ");

​ if([Link]!=null)

[Link]([Link]);

if([Link]!=null)

[Link]([Link]);

​ }

​ }

class Main

​ 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]();

​ }

​ Binarytree bt = new Binarytree();

​ Node root = [Link](arr,n); //1000

​ [Link](root);

​ }

2) import [Link].*;

class Node

​ int data;

​ Node left;

​ Node right;
​ public Node(int d)

​ {

​ data = d;

​ }

class Binarytree

​ public Node insert(String arr[],int n)

​ {

Queue<Node> q = new LinkedList<>();

​ Node root = new Node([Link](arr[0]));

​ [Link](root);

​ int i = 1;

while(![Link]() && i<n)

​ {

​ Node curr = [Link]();

if(!arr[i].equals("null"))

​{

​ [Link] = new Node([Link](arr[i]));


[Link]([Link]);

​}

​ i++;

​ if(i<n && !arr[i].equals("null"))

​{

[Link] = new Node([Link](arr[i]));

[Link]([Link]);

​}

​ i++;

​ }

​ return root;

​ }

public void inorder(Node root)

​ {

​ if(root == null)

​ return;

inorder([Link]);

[Link]([Link]+" ");

inorder([Link]);
​ }

class Main

​ public static void main(String[] args)

​ {

​ Scanner sc = new Scanner([Link]);

​ int n = [Link]();//"1 null 2 3" ==> {"1","null","2","3"}

​ [Link]();

​ String arr[] = [Link]().split(" ");

​ Binarytree bt = new Binarytree();

​ Node root = [Link](arr,n);

[Link](root);

​ }

3)

import [Link].*;

class Node
{

​ int data;

​ Node left;

​ Node right;

​ public Node(int d)

​ {

​ data = d;

​ }

class Binarytree

​ public Node insert(String arr[])

​ {

Queue<Node> q = new LinkedList<>();

​ Node root = new Node([Link](arr[0]));

​ [Link](root);

​ int i = 1,n=[Link];

while(![Link]() && i<n)

​ {
​ Node curr = [Link]();

if(!arr[i].equals("-1"))

​{

​ [Link] = new Node([Link](arr[i]));

[Link]([Link]);

​}

​ i++;

​ if(i<n && !arr[i].equals("-1"))

​{

[Link] = new Node([Link](arr[i]));

[Link]([Link]);

​}

​ i++;

​ }

​ return root;

​ }

public void preorder(Node root)

​ {

​ if(root == null)
​ return;

[Link]([Link]+" ");

preorder([Link]);

preorder([Link]);

​ }

class Main

​ public static void main(String[] args)

​ {

​ Scanner sc = new Scanner([Link]);

​ String arr[] = [Link]().split(" ");

​ Binarytree bt = new Binarytree();

​ Node root = [Link](arr);

[Link](root);

​ }

4) import [Link].*;

class Node
{

​ int data;

​ Node left;

​ Node right;

​ public Node(int d)

​ {

​ data = d;

​ }

class Binarytree

​ public Node insert(int arr[],int n)

​ {

Queue<Node> q = new LinkedList<>();

​ Node root = new Node(arr[0]);

​ [Link](root);

​ int i = 1;

while(![Link]() && i<n)

​ {
​ Node curr = [Link]();

​ [Link] = new Node(arr[i]);

[Link]([Link]);

​ i++;

​ if(i<n)

​{

[Link] = new Node(arr[i]);

[Link]([Link]);

​}

​ i++;

​ }

​ return root;

​ }

​ public int count(Node root)

​ {

​ if(root == null)

​ return 0;

​ return 1 + count([Link]) + count([Link]);

​ }
}

class Main

​ 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]();

​ }

​ Binarytree bt = new Binarytree();

​ Node root = [Link](arr,n); //1000

[Link]([Link](root));

​ }

5) import [Link].*;
class Node

​ int data;

​ Node left;

​ Node right;

​ public Node(int d)

​ {

​ data = d;

​ }

class Binarytree

​ public Node insert(String arr[],int n)

​ {

Queue<Node> q = new LinkedList<>();

​ Node root = new Node([Link](arr[0]));

​ [Link](root);

​ int i = 1;

while(![Link]() && i<n)


​ {

​ Node curr = [Link]();

if(!arr[i].equals("null"))

​{

​ [Link] = new Node([Link](arr[i]));

[Link]([Link]);

​}

​ i++;

​ if(i<n && !arr[i].equals("null"))

​{

[Link] = new Node([Link](arr[i]));

[Link]([Link]);

​}

​ i++;

​ }

​ return root;

​ }

public int height(Node root)

​ {
​ if(root == null)

​ return 0;

​ int lh = height([Link]);

​ int rh = height([Link]);

​ return 1 + [Link](lh,rh);

​ }

class Main

​ public static void main(String[] args)

​ {

​ Scanner sc = new Scanner([Link]);

​ int n = [Link]();//"1 null 2 3" ==> {"1","null","2","3"}

​ [Link]();

​ String arr[] = [Link]().split(" ");

​ Binarytree bt = new Binarytree();

​ Node root = [Link](arr,n); //1000

[Link]([Link](root));

​ }
}

6) import [Link].*;

class Main

​ public static void main(String[] args)

​ {

​ Scanner sc = new Scanner([Link]);

​ int n = [Link]();

​ [Link]();

​ String[] arr = [Link]().split(" ");

​ Node root = bt(arr);

​ int p = [Link]();

​ int q = [Link]();

​ Node LCA = lca(root,p,q);

[Link]([Link]);

​ }

​ public static Node bt(String[] arr)


​ {

if(arr[0].equals("null"))

​return null;

Queue<Node> q = new LinkedList<>();

​ Node root = new Node([Link](arr[0]));

​ int i = 1 , n = [Link];

​ [Link](root);

while(![Link]() && i<n)

​{

​ Node curr = [Link]();

if(!arr[i].equals("null"))

​ {

[Link] = new Node([Link](arr[i]));

[Link]([Link]);

​ }

​ i++;

if(i<n && !arr[i].equals("null"))

​ {

[Link] = new Node([Link](arr[i]));


[Link]([Link]);

​ }

​i++;

​}

​ return root;

​ }

​ public static Node lca(Node root,int p,int q)

​ {

​ if(root == null || [Link] == p || [Link] == q)

​ {

​return root;

​ }

​ Node left = lca([Link],p,q);

​ Node right = lca([Link],p,q);

​ if(left == null)

​ return right;

​ else if(right==null)
​ return left;

​ else

​ return root;

​ }

class Node

​ int data;

​ Node left;

​ Node right;

​ public Node(int data)

​ {

​ [Link] = data;

​ }

7) import [Link].*;

class Node

{
​ int data;

​ Node left;

​ Node right;

​ public Node(int d)

​ {

​ data = d;

​ }

class Binarytree

​ public Node insert(String arr[])

​ {

Queue<Node> q = new LinkedList<>();

​ Node root = new Node([Link](arr[0]));

​ [Link](root);

​ int i = 1,n=[Link];

while(![Link]() && i<n)

​ {

​ Node curr = [Link]();


if(!arr[i].equals("null"))

​{

​ [Link] = new Node([Link](arr[i]));

[Link]([Link]);

​}

​ i++;

​ if(i<n && !arr[i].equals("null"))

​{

[Link] = new Node([Link](arr[i]));

[Link]([Link]);

​}

​ i++;

​ }

​ return root;

​ }

public void rightview(Node root)


​ {

Queue<Node> q = new LinkedList<>();

​ [Link](root);

​ while(![Link]())

​ {

​ int size = [Link]();

​ for(int i=1;i<=size;i++)

​{

​ Node curr = [Link]();

​ if(i == size)

[Link]([Link]+" ");

if([Link]!=null)

[Link]([Link]);

if([Link]!=null)

[Link]([Link]);

​}

​ }

​ }

}
class Main

​ public static void main(String[] args)

​ {

​ Scanner sc = new Scanner([Link]);

​ int n = [Link]();

​ [Link]();

​ String arr[] =[Link]().split(" ");

​ Binarytree bt = new Binarytree();

​ Node root = [Link](arr); //1000

[Link](root);

​ }

8) import [Link].*;

class Node

int data;

​ Node left;
​ Node right;

​ public Node(int d)

​ {

​ data = d;

​ }

class Binarytree

​ public Node insert(int arr[],int n)

​ {

Queue<Node> q = new LinkedList<>();

​ Node root = new Node(arr[0]);

​ [Link](root);

​ int i = 1;

while(![Link]() && i<n)

​ {

​ Node curr = [Link]();

​ [Link] = new Node(arr[i]);

[Link]([Link]);
​ i++;

​ if(i<n)

​ {

[Link] = new Node(arr[i]);

[Link]([Link]);

​}

​ i++;

​ }

​ return root;

​ }

public int leaf(Node root)

​ {

​ if(root == null)

​ return 0;

​ if([Link] == null && [Link] == null)

​ return [Link];

​ return leaf([Link]) + leaf([Link]);

​ }

}
class Main

​ 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]();

​ }

​ Binarytree bt = new Binarytree();

​ Node root = [Link](arr,n); //1000

[Link]([Link](root));

​ }

9) import [Link].*;

class Node
{

​ int data;

​ Node left;

​ Node right;

​ public Node(int d)

​ {

​ data = d;

​ }

class Binarytree

​ public Node insert(int arr[],int n)

​ {

Queue<Node> q = new LinkedList<>();

​ Node root = new Node(arr[0]);

​ [Link](root);

​ int i = 1;

while(![Link]() && i<n)

​ {
​ Node curr = [Link]();

​ [Link] = new Node(arr[i]);

[Link]([Link]);

​ i++;

​ if(i<n)

​ {

[Link] = new Node(arr[i]);

[Link]([Link]);

​}

​ i++;

​ }

​ return root;

​ }

​ public void zigzag(Node root)

​ {

Queue<Node> q = new LinkedList<>();

​ [Link](root);

​ boolean LtoR = true;

while(![Link]())
​ {

​ int size = [Link]();

​ int arr[] = new int[size];

​ for(int i=0;i<size;i++)

​{

​ Node curr = [Link]();

​ int ind=0;

​ if(LtoR == true)

​ ind = i;

​ else

​ ind = size - 1- i;

arr[ind] = [Link];

if([Link]!=null)

[Link]([Link]);

if([Link]!=null)

​ [Link]([Link]);

​}

​ for(int i=0;i<size;i++)
[Link](arr[i]+" ");

​ LtoR = !LtoR;

[Link]();

​ }

​ }

class Main

​ 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]();

​ }
​ Binarytree bt = new Binarytree();

​ Node root = [Link](arr,n); //1000

[Link](root);

​ }

​ PostClass

2) import [Link].*;

class Node {

​ int data;

​ Node left, right;

Node(int data) {
​ [Link] = data;

​ }

public class Main {

​ static Node buildTree(int[] arr) {

​ if ([Link] == 0) return null;

​ Node root = new Node(arr[0]);

Queue<Node> q = new LinkedList<>();

​ [Link](root);

​ int i = 1;

​ while (i < [Link]) {

​Node current = [Link]();

​if (i < [Link]) {

[Link] = new Node(arr[i++]);

​ [Link]([Link]);

​}

​if (i < [Link]) {

[Link] = new Node(arr[i++]);


[Link]([Link]);

​}

​ }

​ return root;

​ }

​ static int leftmostInLastRow(Node root) {

Queue<Node> q = new LinkedList<>();

​ [Link](root);

​ int leftmost = [Link];

​ while (![Link]()) {

​int size = [Link]();

​for (int i = 0; i < size; i++) {

​ Node temp = [Link]();

​ if (i == 0) leftmost = [Link];

​ if ([Link] != null)

[Link]([Link]);

​ if ([Link] != null)

[Link]([Link]);
​}

​ }

​ return leftmost;

​ }

​ 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]();

​ Node root = buildTree(arr);

[Link](leftmostInLastRow(root));

​ }

3) import [Link].*;

class Node {
​ int data;

​ Node left, right;

​ Node(int data) {

​ [Link] = data;

​ }

public class Main {

​ static Node buildTree(int[] arr) {

​ if ([Link] == 0) return null;

​ Node root = new Node(arr[0]);

Queue<Node> q = new LinkedList<>();

​ [Link](root);

​ int i = 1;

​ while (i < [Link]) {

​Node current = [Link]();

​if (i < [Link]) {

[Link] = new Node(arr[i++]);

[Link]([Link]);
​}

​if (i < [Link]) {

[Link] = new Node(arr[i++]);

​ [Link]([Link]);

​}

​ }

​ return root;

​ }

​ static void invert(Node root) {

​ if (root == null) return;

​ Node temp = [Link];

​ [Link] = [Link];

​ [Link] = temp;

invert([Link]);

invert([Link]);

​ }

​ static void printLevelOrder(Node root) {


Queue<Node> q = new LinkedList<>();

​ [Link](root);

​ while (![Link]()) {

​Node temp = [Link]();

​[Link]([Link] + " ");

​if ([Link] != null) [Link]([Link]);

​if ([Link] != null) [Link]([Link]);

​ }

​ }

​ 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]();

​ Node root = buildTree(arr);

​ invert(root);

printLevelOrder(root);
​ }

4) import [Link].*;

class Node {

​ int data;

​ Node left, right;

​ Node(int data) {

​ [Link] = data;

​ }

public class Main {

​ static Node buildTree(int[] arr) {

​ if ([Link] == 0)

​ return null;

​ Node root = new Node(arr[0]);

​ Queue<Node> q = new LinkedList<>();


​ [Link](root);

​ int i = 1;

​ while (i < [Link]) {

​Node current = [Link]();

​if (i < [Link]) {

[Link] = new Node(arr[i++]);

[Link]([Link]);

​}

​if (i < [Link]) {

[Link] = new Node(arr[i++]);

[Link]([Link]);

​}

​ }

​ return root;

​ }

​ static boolean isSumTree(Node root) {

​ return check(root)[1] == 1;

​ }
​ static int[] check(Node root) {

​ if (root == null) return new int[]{0, 1};

​ if ([Link] == null && [Link] == null) return new


int[]{[Link], 1};

​ int[] left = check([Link]);

int[] right = check([Link]);

​ int valid = (left[1] == 1 && right[1] == 1 && [Link] == left[0]


+ right[0]) ? 1 : 0;

​ return new int[]{left[0] + right[0] + [Link], valid};

​ }

​ 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]();

​ Node root = buildTree(arr);

[Link](isSumTree(root) ? "Yes" : "No");


​ }

___________________________________________________

Binary Search Tree


Inclass
1)​ import [Link].*;

class Node {
int data;
Node left, right;
Node(int data) {
[Link] = data;
}
}

public class Main {


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

static void inorder(Node root) {


if (root == null) return;
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
}

public static void main(String[] args) {


Scanner sc = new Scanner([Link]);
int n = [Link]();
Node root = null;
for (int i = 0; i < n; i++) {
int data = [Link]();
root = insert(root, data);
}
inorder(root);
}
}

2 import [Link].*;

class Node {
int data;
Node left, right;
Node(int data) {
[Link] = data;
}
}

public class Main {


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

static Node search(Node root, int val) {


if (root == null || [Link] == val)
return root;
if (val < [Link])
return search([Link], val);
else
return search([Link], val);
}

static void inorder(Node root) {


if (root == null) return;
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
}

public static void main(String[] args) {


Scanner sc = new Scanner([Link]);
int n = [Link]();
Node root = null;
for (int i = 0; i < n; i++) {
root = insert(root, [Link]());
}
int val = [Link]();
Node result = search(root, val);
if (result == null) {
[Link]("Book not found");
} else {
[Link]("Book found! Subtree rooted at " + val + ":");
inorder(result);
}
}
}

3 import [Link].*;

class Node {
int data;
Node left, right;
Node(int data) {
[Link] = data;
}
}

public class Main {


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

static Node delete(Node root, int key) {


if (root == null)
return null;
if (key < [Link])
[Link] = delete([Link], key);
else if (key > [Link])
[Link] = delete([Link], key);
else {
if ([Link] == null)
return [Link];
else if ([Link] == null)
return [Link];
[Link] = minValue([Link]);
[Link] = delete([Link], [Link]);
}
return root;
}

static int minValue(Node root) {


int min = [Link];
while ([Link] != null) {
min = [Link];
root = [Link];
}
return min;
}

static void inorder(Node root) {


if (root == null)
return;
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
}

public static void main(String[] args) {


Scanner sc = new Scanner([Link]);
int n = [Link]();
Node root = null;
for (int i = 0; i < n; i++) {
root = insert(root, [Link]());
}
int key = [Link]();
root = delete(root, key);
inorder(root);
}
}

4 import [Link].*;
class Node {
int data;
Node left, right;
Node(int data) {
[Link] = data;
}
}

public class Main {


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

static Node trimBST(Node root, int low, int high) {


if (root == null)
return null;
if ([Link] < low)
return trimBST([Link], low, high);
if ([Link] > high)
return trimBST([Link], low, high);
[Link] = trimBST([Link], low, high);
[Link] = trimBST([Link], low, high);
return root;
}

static void preorder(Node root) {


if (root == null)
return;
[Link]([Link] + " ");
preorder([Link]);
preorder([Link]);
}

public static void main(String[] args) {


Scanner sc = new Scanner([Link]);
int n = [Link]();
Node root = null;
for (int i = 0; i < n; i++) {
root = insert(root, [Link]());
}
int low = [Link]();
int high = [Link]();
root = trimBST(root, low, high);
preorder(root);
}
}

5 import [Link].*;

class Node {
int data;
Node left, right;
Node(int data) {
[Link] = data;
}
}

public class Main {


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

static int kthSmallest(Node root, int k) {


Stack<Node> stack = new Stack<>();
Node current = root;
int count = 0;
while (current != null || ![Link]()) {
while (current != null) {
[Link](current);
current = [Link];
}
current = [Link]();
count++;
if (count == k)
return [Link];
current = [Link];
}
return -1;
}

public static void main(String[] args) {


Scanner sc = new Scanner([Link]);
int n = [Link]();
Node root = null;
for (int i = 0; i < n; i++)
root = insert(root, [Link]());
int k = [Link]();
int result = kthSmallest(root, k);
if (result == -1)
[Link]("k is out of range");
else
[Link](result);
}
}

6 import [Link].*;

class Node {
int data;
Node left, right;
Node(int data) {
[Link] = data;
}
}

public class Main {


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

static boolean hasPathSum(Node root, int sum) {


if (root == null)
return false;
if ([Link] == null && [Link] == null)
return sum == [Link];
return hasPathSum([Link], sum - [Link]) || hasPathSum([Link], sum - [Link]);
}

public static void main(String[] args) {


Scanner sc = new Scanner([Link]);
int n = [Link]();
Node root = null;
for (int i = 0; i < n; i++)
root = insert(root, [Link]());
int targetSum = [Link]();
[Link](hasPathSum(root, targetSum));
}
}

7 import [Link].*;

class Node {
int data;
Node left, right;
Node(int data) {
[Link] = data;
}
}

public class Main {


static Node insert(int arr[] , int n) {
Queue<Node> q = new LinkedList<>();
Node root = new Node(arr[0]);
[Link](root);
int i = 1;
while(![Link]() && i<n)
{
Node curr = [Link]();
[Link] = new Node(arr[i]);
[Link]([Link]);
i++;
if(i<n)
{
[Link] = new Node(arr[i]);
[Link]([Link]);
}
i++;
}
return root;
}

static boolean isValidBST(Node root, int min, int max) {


if (root == null)
return true;
if ([Link] <= min || [Link] >= max)
return false;
return isValidBST([Link], min, [Link]) && isValidBST([Link], [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]();
Node root = insert(arr,n);
if (isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE))
[Link]("The book collection is a valid binary search tree.");
else
[Link]("The book collection is NOT a valid binary search tree.");
}
}

Postclass

1)​ import [Link].*;

class Node {
int data;
Node left, right;
Node(int data) {
[Link] = data;
}
}

public class Main {


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

static Node lowestCommonAncestor(Node root, int p, int q) {


if (root == null)
return null;
if ([Link] > p && [Link] > q)
return lowestCommonAncestor([Link], p, q);
if ([Link] < p && [Link] < q)
return lowestCommonAncestor([Link], p, q);
return root;
}

public static void main(String[] args) {


Scanner sc = new Scanner([Link]);
int n = [Link]();
Node root = null;
for (int i = 0; i < n; i++)
root = insert(root, [Link]());
int p = [Link]();
int q = [Link]();
Node lca = lowestCommonAncestor(root, p, q);
[Link]([Link]);
}
}

2 import [Link].*;

class ListNode {
int val;
ListNode next;
ListNode(int val)
{
[Link] = val;
}
}

class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
[Link] = val;
}
}

public class Main {


static ListNode head;

static int getLength(ListNode node) {


int len = 0;
while (node != null) {
len++;
node = [Link];
}
return len;
}

static TreeNode sortedListToBST(int n) {


if (n <= 0) return null;
TreeNode left = sortedListToBST(n / 2);
TreeNode root = new TreeNode([Link]);
head = [Link];
[Link] = left;
[Link] = sortedListToBST(n - n / 2 - 1);
return root;
}

static void preorder(TreeNode root) {


if (root == null)
return;
[Link]([Link] + " ");
preorder([Link]);
preorder([Link]);
}

public static void main(String[] args) {


Scanner sc = new Scanner([Link]);
int n = [Link]();
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
for (int i = 0; i < n; i++) {
[Link] = new ListNode([Link]());
curr = [Link];
}
head = [Link];
TreeNode root = sortedListToBST(n);
preorder(root);
}
}

3 import [Link].*;

class Node {
int price;
Node left, right;
Node(int price) { [Link] = price; }
}

public class Main {


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

static Node findMin(Node root) {


while ([Link] != null)
root = [Link];
return root;
}

public static void main(String[] args) {


Scanner sc = new Scanner([Link]);
int n = [Link]();
Node root = null;
for (int i = 0; i < n; i++) {
root = insert(root, [Link]());
}
Node minNode = findMin(root);
[Link]([Link]);
}
}
4 import [Link].*;

class Node {
int height;
Node left, right;
Node(int height) { [Link] = height; }
}

public class Main {


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

static void leftView(Node root) {


if (root == null) return;
Queue<Node> q = new LinkedList<>();
[Link](root);
while (![Link]()) {
int size = [Link]();
for (int i = 0; i < size; i++) {
Node node = [Link]();
if (i == 0)
[Link]([Link]);
if ([Link] != null)
[Link]([Link]);
if ([Link] != null)
[Link]([Link]);
}
}
}

public static void main(String[] args) {


Scanner sc = new Scanner([Link]);
int n = [Link]();
Node root = null;
for (int i = 0; i < n; i++) {
root = insert(root, [Link]());
}
leftView(root);
}
}

5 import [Link].*;

class Node {
int id;
Node left, right;
Node(int id) { [Link] = id; }
}

public class Main {


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

static Node find(Node root, int key) {


if (root == null || [Link] == key)
return root;
if (key < [Link])
return find([Link], key);
else
return find([Link], key);
}

static Node minValueNode(Node node) {


while ([Link] != null)
node = [Link];
return node;
}

static Node inorderSuccessor(Node root, int key) {


Node current = find(root, key);
if (current == null)
return null;
if ([Link] != null)
return minValueNode([Link]);
Node succ = null;
Node ancestor = root;
while (ancestor != current) {
if ([Link] < [Link]) {
succ = ancestor;
ancestor = [Link];
} else ancestor = [Link];
}
return succ;
}

public static void main(String[] args) {


Scanner sc = new Scanner([Link]);
int n = [Link]();
Node root = null;
for (int i = 0; i < n; i++) {
root = insert(root, [Link]());
}
int key = [Link]();
Node succ = inorderSuccessor(root, key);
if (succ != null) [Link]([Link]);
else [Link]("No Inorder Successor");
}
}

You might also like