tree data structure
insert Node in bst
import java.io.*;
class GFG
{
Node root;
class Node
{
int data;
Node left,right;
Node(int d1)
{
data=d1;
left=right=null;
}
}
public Node insert(int d11)
{
root=hello_insert(root,d11);
return root;
}
public Node hello_insert(Node root,int d11)
{
// Node n1=new Node(d11);
if(root==null)
{
root=new Node(d11);
}
else
{
if(root.data>d11)
{
root.left=hello_insert(root.left,d11);
}
else
{
root.right=hello_insert(root.right,d11);
}
}
return root;
}
public void inorder()
{
root=inorder_print(root);
}
public Node inorder_print(Node root)
{
if(root!=null)
{
inorder_print(root.left);
System.out.print(root.data);
inorder_print(root.right);
}
return root;
}
public static void main (String[] args) {
GFG n1=new GFG();
n1.insert(1);
n1.insert(2);
n1.insert(3);
n1.insert(4);
n1.insert(5);
n1.inorder();
}
}
Level order without recursion
used level order traversal of tree..using implementation of queue.
public void print(Node root)
{
Queue q=new LinkedList(); //implemented concept of level order.
q.add(root);
while(!q.isEmpty())
{
Node n1=(Node)q.poll();
System.out.print(n1.data);
if(n1.left!=null)
{
q.offer(n1.left);
}
if(n1.right!=null)
{
q.offer(n1.right);
}
}
}
Inorder traversal without recursion using stack
1.pushing the root node
2.pushing the left to stack and moving toward left till left will null.
3.Now
1>poping and printing the peek
ii>using if checking right if right is not null then push
iii>.inside if use step 2.
Run till stack will be empty.
public void print(Node root)
{
if(root==null)
{
return;
}
Stack<Node> s=new Stack<Node>();
s.push(root);
while(!s.isEmpty())
{
while(root.left!=null) //pushing till left will be null
{
s.push(root.left);
root=root.left;
}
while(s.size()>0)
{
Node n1=s.pop(); //poping and print the top
System.out.print(n1.data) //midwhile checking right is null or not null if it is not null push that to stack
if(n1.right!=null)
{
s.push(n1.right);
n1=n1.right;
while(n1.left!=null) //now checking right of left if it is not null push that to stack
{
s.push(n1.left);
n1=n1.left;
}
}
}
}
}
PreOrder traversal without using recursion
1.push root node to stack
2.print the top node and perform pop operation Now push the right node then left node using if condition...repeat this till stack will empty.
public void print(Node root)
{
if(root==null)
{
return;
}
else
{
Stack<Node> s=new Stack<Node>();
s.push(root);
while(s.size()>0)
{
Node n1=s.peek();
System.out.println(n1.data); //printing the peek node
s.pop(); //and performing the pop operation
if(n1.right!=null)
{
s.push(n1.right); //Now pushing the right node
//n1=n1.right;
}
if(n1.left!=null)
{
s.push(n1.left); //And pushing the left Node
//n1=n1.right;
}
}
}
PostOrder traversal without using recursion
- Push root to first stack
- Pop top node from first stack and push to second Now Push left node in first stack and the right node in first stack using if perform these till first stack will be empty
- Now print the top node from second stack and perform pop for each iteration till second stack will empty.
public void print(Node root)
{
Stack<Node> s1=new Stack<Node>();
Stack<Node> s2=new Stack<Node>();
s1.push(root);
while(!s1.isEmpty())
{
Node n1=s1.pop(); //popping from first stack
s2.push(n1);//pushing to second stack
if(n1.left!=null)
{
s1.push(n1.left); //pushing left node
// n1=n1.left;
}
if(n1.right!=null)
{
s1.push(n1.right); //pushing right node
// n1=n1.right;
}
}
while(!s2.isEmpty()) //now popping and printing the top node
{
Node n2=s2.pop();
System.out.print(n2.data);
}
}
1 find the maximum element in bst.
import java.util.*;
import java.io.*;
class GFG
{
static Node root;
class Node
{
int data;
Node left,right;
Node(int d1)
{
data=d1;
left=right=null;
}
}
public void insert(int d1)
{
root=insert_data(root,d1);
}
public Node insert_data(Node root,int d1)
{
if(root==null)
{
root=new Node(d1);
}
else
{
if(d1<root.data)
{
root.left=insert_data(root.left,d1);
}
else
{
root.right=insert_data(root.right,d1);
}
}
return root;
}
public void inorder()
{
root=inorder_print(root);
}
public Node inorder_print(Node root)
{
if(root!=null)
{
inorder_print(root.left);
System.out.print(root.data);
inorder_print(root.right);
}
return root;
}
public int max_find(Node root)
{
int max_value=Integer.MIN_VALUE;
if(root!=null)
{
int leftmax=max_find(root.left);//its maintaind stack
int rightmax=max_find(root.right);//its maintaining stack
if(leftmax>rightmax)//now poping and compairing
{
max_value=leftmax;
}
else
{
max_value=rightmax;
}
if(root.data>max_value)
{
max_value=root.data;
}
}
return max_value;
}
/*
if(root==null)
{
return Integer.MIN_VALUE;
}
int mx=root.data;
int left1=print(root.left);
int right1=print(root.right);
if(mx<left1)
{
mx=left1;
}
if(mx<right1)
{
mx=right1;
}
return mx;
*/
public static void main(String[] args)
{
GFG l1=new GFG();
l1.insert(1);
l1.insert(2);
l1.insert(3);
l1.insert(4);
l1.insert(5);
// l1.inorder();
System.out.print(l1.max_find(root));
}
}
2.searching of element in tree
import java.util.*;
import java.io.*;
class GFG
{
static Node root;
class Node
{
int data;
Node left,right;
Node(int d1)
{
data=d1;
eft=right=null;
}
}
public void insert(int d1)
{
root=insert_data(root,d1);
}
public Node insert_data(Node root,int d1)
{
if(root==null)
{
root=new Node(d1);
}
else
{
if(d1<root.data)
{
root.left=insert_data(root.left,d1);
}
else
{
root.right=insert_data(root.right,d1);
}
}
return root;
}
public void inorder()
{
root=inorder_print(root);
}
public Node inorder_print(Node root)
{
if(root!=null)
{
inorder_print(root.left);
System.out.print(root.data);
inorder_print(root.right);
}
return root;
}
public int max_find(Node root)
{
int max_value=Integer.MIN_VALUE;
if(root!=null)
{
int leftmax=max_find(root.left);
int rightmax=max_find(root.right);
if(leftmax>rightmax)
{
max_value=leftmax;
}
else
{
max_value=rightmax;
}
if(root.data>max_value)
{
max_value=root.data;
}
}
return max_value;
}
public boolean find(Node root,int d1)
{
if(root==null)
{
return false;
}
else
{
if(root.data==d1)
{
return true;
}
else
{
return (find(root.left,d1)|| find(root.right,d1)); //returning left and right
}
}
}
public static void main(String[] args)
{
GFG l1=new GFG();
l1.insert(1);
l1.insert(2);
l1.insert(3);
l1.insert(4);
l1.insert(5);
// l1.inorder();
System.out.print(l1.max_find(root));
System.out.print(l1.find(root,3));
}
}
3.find total no of element in binary search tree.
For non recursive use level order traversal.
This is for recursive method.
int count =0;
public int totalnodes(Node root)
{
int leftc=0;int rightc=0;
if(root!=null)
{
leftc=totalnodes(root.left); //using the concept of height we are calculating no of node
rightc=totalnodes(root.right);
count++;
}
return count;
}
/*
public int print(Node root)
{
if(root==null)
{
return 0;
}
else
{
return 1+ print(root.left) + print(root.right);
}
}
*/
4 Method to find height of tree.
It will tell number of node in longest path starting from 1.
public int height(Node root)
{
if(root!=null)
{
int leftc=inorder(root.left);
int rightc=inorder(root.right);
if(leftc>rightc)
{
return leftc+1; // when node will null the this will start working.
}
else
{
return rightc+1;
}
}
else
{
return 0; //1st this will work then other return will work..
}
}
5.reverse level order
Means print height wise
void reverseLevelOrder(Node root)
{
int h = height(root);
int i;
for (i = h; i >= 1; i--)
//THE ONLY LINE DIFFERENT FROM NORMAL LEVEL ORDER
{
printGivenLevel(root, i);
}
}
/* Print nodes at a given level */
void printGivenLevel(Node root, int level)
{
if (root == null)
return;
if (level == 1)
System.out.print(root.data + " ");
else if (level > 1)
{
printGivenLevel(root.left, level - 1);
printGivenLevel(root.right, level - 1);
/* if u want to print right to left then it will be useful.
printGivenLevel(root.right, level - 1);
printGivenLevel(root.left, level - 1);
*/
}
}
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(Node root)
{
if (root == null)
return 0;
else
{
/* compute the height of each subtree */
int lheight = height(root.left);
int rheight = height(root.right);
/* use the larger one */
if (lheight > rheight)
return (lheight + 1);
else
return (rheight + 1);
}
}
5.Boundary order traversal
->print the left boundary
->print the leaf node
->print the right node
void printBoundaryLeft(Node node)
{
if (node != null)
{
if (node.left != null)
{
// to ensure top down order, print the node
// before calling itself for left subtree
System.out.print(node.data + " ");
printBoundaryLeft(node.left);
}
else if (node.right != null)
{
System.out.print(node.data + " ");
printBoundaryLeft(node.right);
}
// do nothing if it is a leaf node, this way we avoid
// duplicates in output
}
}
// A function to print all right boundary nodes, except a leaf node
// Print the nodes in BOTTOM UP manner
void printBoundaryRight(Node node)
{
if (node != null)
{
if (node.right != null)
{
// to ensure bottom up order, first call for right
// subtree, then print this node
printBoundaryRight(node.right);
System.out.print(node.data + " ");
}
else if (node.left != null)
{
printBoundaryRight(node.left);
System.out.print(node.data + " ");
}
// do nothing if it is a leaf node, this way we avoid
// duplicates in output
}
}
// A function to do boundary traversal of a given binary tree
//print the leaf node
public void printLeaves(Node root)
{
if(root!=null)
{
if(root.left==null && root.right==null)
{
System.out.print(root.data);
}
printLeaves(root.left);
printLeaves(root.right);
}
}
void printBoundary(Node node)
{
if (node != null)
{
System.out.print(node.data + " ");
// Print the left boundary in top-down manner.
printBoundaryLeft(node.left);
// Print all leaf nodes
printLeaves(node);
//printLeaves(node.right);
// Print the right boundary in bottom-up manner
printBoundaryRight(node.right);
}
}
6.minimum depth of binary tree
public int height(Node root)
{
if(root==null)
{
return 0;
}
else
{
int left1=height(root.left);
int right1=height(root.right);
if(left1>right1) // bcz we hv to cal. Min depth other wise for enqu.will be in opposite direction.
{
return right1 +1;
}
else
{
return left1+1;
}
}
}
7.CHECK TWO TREE ARE MIRROR IMAGE OF EACH other
Public boolean checkStructuralSameTree(Node root1,Node root2)
{
if(root1==null && root2==null)
{
return true;
}
if(root1==null || root2==null)
{
return false;
}
else return (root1.data==root2.data) && (checkStructuralSameTree(root1.left,root2.right) && checkStructuralSameTree(root1.right,root2.left) )
}
8.To find width of binary tree
Without recursion use level order traversal. And using a maxcount of queue find maximum no of element on the particular level.
With recursion
public void pass_height_wise_and_cal_max__node_on_level(Node root)
{
int max=0;
int h=height(root); //find height
//System.out.print(h);
for(int i=1;i<=h;i++)
{
int temp=width(root,i);
if(temp>max)
{
max=temp;
}
}
System.out.print(max);
}
public int width(Node root,int level)
{
if(root==null)
{
return 0;
}
else if(level==1)
{
return 1; //similar to print level just we are returning 1 instead of printing
}
else
{
return width(root.left,level-1) + width(root.right,level-1);//we are just adding instead of separate call of left and right
}
}
int height(Node root)
{
if(root==null)
{
return 0;
}
else
{
int l1=height(root.left);
int r1=height(root.right);
if(l1>r1)
{
return l1 +1;
}
else
{
return r1 +1;
}
}
}
9 find the diameter of binary tree.
Find max of (rightsubtree height and leftsub tree height) and max(diameter(left),diameter(right)))
int diameter(Node root)
{
/* base case if tree is empty */
if (root == null)
return 0;
/* get the height of left and right sub trees */
int lheight = height(root.left);
int rheight = height(root.right);
/* get the diameter of left and right subtrees */
int ldiameter = diameter(root.left);
int rdiameter = diameter(root.right);
/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */
return Math.max(lheight + rheight + 1,
Math.max(ldiameter, rdiameter));
}
10.find the maximum sum at level
Used level order traversal using recusrion
int sum=0;
static int max=0;
public void inorder_print(Node root)
{
int h=height(root);
for(int i=h;i>=1;i--)
{
level(root,i);
if(max<sum) //for each height calculating height and checking from max variable.
{
max=sum;
}
sum=0;
}
}
public void level(Node root,int lev)
{
if(root==null)
{
return;
}
if(lev==1)
{
sum= sum +root.data;
//System.out.println(sum);
}
else if(lev>1)
{
level(root.left,lev-1);
level(root.right,lev-1);
}
}
int height(Node root)
{
if(root==null)
{
return 0;
}
else
{
int l1=height(root.left);
int r1=height(root.right);
if(l1>r1)
{
return l1 +1;
}
else
{
return r1 +1;
}
}
}
static int max=0;
public void inorder_print(Node root)
{
int h=height(root);
for(int i=h;i>=1;i--)
{
level(root,i);
if(max<sum) //for each height calculating height and checking from max variable.
{
max=sum;
}
sum=0;
}
}
public void level(Node root,int lev)
{
if(root==null)
{
return;
}
if(lev==1)
{
sum= sum +root.data;
//System.out.println(sum);
}
else if(lev>1)
{
level(root.left,lev-1);
level(root.right,lev-1);
}
}
int height(Node root)
{
if(root==null)
{
return 0;
}
else
{
int l1=height(root.left);
int r1=height(root.right);
if(l1>r1)
{
return l1 +1;
}
else
{
return r1 +1;
}
}
}
11.print root to leave all path
public void print_data(Node root)
{
int[] n1=new int[1000];
print_data_recr(root,n1,0);
}
public void print_data_recr(Node root,int n1[],int d1)
{
if(root==null) // to return from recursion
{
return;
}
n1[d1]=root.data;
d1++;
if(root.left==null && root.right==null) //if leaf then print root to leaf
{
print(n1,d1);
}
else
{
print_data_recr(root.left,n1,d1);
print_data_recr(root.right,n1,d1);
}
}
public void print(int[] n1,int d1) // to [print path
{
for(int i=0;i<d1;i++)
{
System.out.print(n1[i]+" ");
}
System.out.println();
}
12.Root to leaf sum exist or not.
Use same method as print root to leave.
public void print_data(Node root)
{
int[] n1=new int[1000];
print_data_recr(root,n1,0);
}
public void print_data_recr(Node root,int n1[],int d1)
{
if(root==null)
{
return;
}
n1[d1]=root.data;
d1++;
if(root.left==null && root.right==null)
{
print(n1,d1);
}
else
{
print_data_recr(root.left,n1,d1);
print_data_recr(root.right,n1,d1);
}
}
public void print(int[] n1,int d1)
{
int t=0;
for(int i=0;i<d1;i++)
{
System.out.print(n1[i]+" ");
t=sum-n1[i]; //if sum will be available then automatically t will goes to zero.
if(t==0)
{
System.out.println("yes");
return;
}
}
/*
for(int i=0;i<d1;i++)
{
// System.out.print(a[i]+" ");
p=p+a[i];
}
if(p-t==0)
{
System.out.print(p+"=yes");
System.exit(0);
}
*/
System.out.println();
}
12.Maximum Path Sum in a Binary Tree
public int get(Node root)
{
int[] a=new int[1];
a[0]=Integer.MIN_VALUE;
calculate(root,a);
return a[0];
}
public int calculate(Node root,int[] a)
{
if(root==null)
{
return 0;
}
int l=calculate(root.left,a);
int r=calculate(root.right,a);
int current=Math.max(root.data,Math.max(root.data+l,root.data+r));
a[0]=Math.max(a[0],Math.max(current,root.data+l+r));
return current;
}
public static void main (String[] args)
{
GFG n1=new GFG();
n1.insert(99);
n1.insert(2);
n1.insert(3);
n1.insert(4);
n1.insert(0);
n1.insert(30);
n1.insert(15);
n1.insert(45);
n1.insert(101);
n1.insert(-1);
n1.insert(1);
System.out.print(n1.get(root));
}
13.Top view of a tree using level order and hashMap
public void top_view(Node root)
{
if(root==null)
{
return;
}
else
{
Queue<Node> q=new LinkedList<Node>();
HashMap<Integer,Integer> h1=new HashMap<Integer,Integer>();//real hashmap
HashMap<Integer,Integer> h2=new HashMap<Integer,Integer>();//to get key
q.add(root);
// int value=0;
h1.put(0,root.data);
h2.put(root.data,0);
while(q.size()>0)
{
Node n1=q.poll();
int r1=h2.get(n1.data);
if(n1.left!=null)
{
q.add(n1.left);
if(!h1.containsKey(r1-1))
{
h1.put(r1-1,n1.left.data);
}
h2.put(n1.left.data,r1-1);
}
if(n1.right!=null)
{
q.add(n1.right);
if(!h1.containsKey(r1+1))
{
h1.put(r1+1,n1.right.data);
}
h2.put(n1.right.data,r1+1);
}
}
Map<Integer,Integer> m1=new HashMap<Integer,Integer>(h1); //used for sorting the key
Set s1=m1.entrySet();
Iterator it=s1.iterator();
while(it.hasNext())
{
Map.Entry me = (Map.Entry)it.next();
System.out.println(me.getKey()+":"+me.getValue());
}
}
}
Bottom view
public void top_view(Node root)
{
if(root==null)
{
return;
}
else
{
Queue<Node> q=new LinkedList<Node>();
HashMap<Integer,Integer> h1=new HashMap<Integer,Integer>();
HashMap<Integer,Integer> h2=new HashMap<Integer,Integer>();
q.add(root);
// int value=0;
h1.put(1,root.data);
h2.put(root.data,1);
while(q.size()>0)
{
Node n1=q.poll();
int r1=h2.get(n1.data);
if(n1.left!=null)
{
q.add(n1.left);
h1.put(r1-1,n1.left.data); //if same same key value will come it will automatic updated
h2.put(n1.left.data,r1-1);
}
if(n1.right!=null)
{
q.add(n1.right);
h1.put(r1+1,n1.right.data);
h2.put(n1.right.data,r1+1);
}
}
Map<Integer,Integer> m1=new HashMap<Integer,Integer>(h1);
Set s1=m1.entrySet();
Iterator it=s1.iterator();
while(it.hasNext())
{
Map.Entry me = (Map.Entry)it.next();
System.out.println(me.getKey()+":"+me.getValue());
}
}
}
14.root to leaf sum is existing or not using recursion
public boolean print_given_sum(Node root,int sum)
{
if(root!=null)
{
if(root.left==null && root.right==null && root.data==sum)
{
return true;
}
else
return print_given_sum(root.left,sum-root.data) || print_given_sum(root.left,sum-root.data);
}
else
{
return false;
}
}
15.Converting tree to mirror of itself. Means exchange the left and right of non leaf node.
public Node exchange_non_leaf_mirroring(Node root)
{
if(root!=null)
{
exchange_non_leaf_mirroring(root.left);
exchange_non_leaf_mirroring(root.right);
Node temp=root.left;
root.left=root.right;
root.right=temp;
}
return root;
}
15 .lowest common anchester.
LCA of 10 and 14 is 12
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20
//important its for binary search tree
Node lca(Node node, int n1, int n2)
{
if (node == null)
return null;
// If both n1 and n2 are smaller than root, then LCA lies in left
if (node.data > n1 && node.data > n2)
return lca(node.left, n1, n2);
// If both n1 and n2 are greater than root, then LCA lies in right
if (node.data < n1 && node.data < n2)
return lca(node.right, n1, n2);
return node;
}
//Its for binary tree
public Node print(Node root,int d1,int d2)
{
if(root==null)
{
return null;
}
if(root.data==d1 || root.data==d2)
{
return root;
}
Node l1=print(root.left,d1,d2);
Node r1=print(root.right,d1,d2);
if( l1!=null && r1!=null)
{
return root;
}
return (l1!=null)?l1 : r1;
}
16.zigzag traversal(spiral traversal from level order)
public void zigzag(Node root)
{
Stack<Node> s1=new Stack<Node>();
Stack<Node> s2=new Stack<Node>();
s1.push(root);
while(s1.size()>0 || s2.size()>0)
{
while(s1.size()>0) //while s1 size() greater than zero
{
Node n1=s1.pop(); //pop and print
System.out.print(n1.data+" ");
if(n1.left!=null) // first left than right
{
s2.push(n1.left);
}
if(n1.right!=null)
{
s2.push(n1.right);
}
}
while(s2.size()>0)
{
Node n1=s2.pop();
System.out.print(n1.data+" ");
if(n1.right!=null) //first right then left
{
s1.push(n1.right);
}
if(n1.left!=null)
{
s1.push(n1.left);
}
}
}
}
17.print all anchester of a node of binary tree.
boolean printAncestors(Node node, int target)
{
/* base cases */
if (node == null)
return false;
if (node.data == target)
return true;
/* If target is present in either left or right subtree
of this node, then print this node */
//first checking all left ancester
if (printAncestors(node.left, target) || printAncestors(node.right, target))
{
System.out.print(node.data + " ");
return true;
}
/* else return false */
return false;
}
18: vertical sum of binary tree
public void vertical(HashMap<Integer,Integer> h1,Node root,int c)
{
if(root==null)
{
return;
}
else
{
if(root.left!=null)
{
vertical(h1,root.left,c-1);
}
if(root.right!=null)
{
vertical(h1,root.right,c+1);
}
int data=0;
if(h1.containsKey(c))
{
data=h1.get(c);
}
h1.put(c,root.data+data);
}
}
public void ver_sum(Node root)
{
HashMap<Integer,Integer> h1=new HashMap<Integer,Integer>();
vertical(h1,root,0);
TreeMap<Integer,Integer> ma=new TreeMap<Integer,Integer>(h1);
Set s1=ma.entrySet();
Iterator ir=s1.iterator();
while(ir.hasNext())
{
Map.Entry m1=(Map.Entry)ir.next();
System.out.println(m1.getKey()+":"+m1.getValue());
}
}
Note :Top view
static public void verticle(Node root,HashMap<Integer,Integer> h1,int c)
{
if(root==null)
{
return;
}
if(root.left!=null)
{
verticle(root.left,h1,c-1);
}
if(root.right!=null)
{
verticle(root.right,h1,c+1);
}
h1.put(c,root.data);
}
Bottom view:
static public void verticle(Node root,HashMap<Integer,Integer> h1,int c)
{
if(root==null)
{
return;
}
if(root.left!=null)
{
verticle(root.left,h1,c-1);
}
if(root.right!=null)
{
verticle(root.right,h1,c+1);
}
if(!h1.containsKey(c))
{
h1.put(c,root.data);
}
}
Print in vertical order
import java.util.*;
import java.io.*;
class GFG
{
static Node root;
class Node
{
Node left,right;
int data;
Node(int d1)
{
data=d1;
left=right=null;
}
}
public void insert(int d1)
{
root=insert_data(root,d1);
}
public Node insert_data(Node root,int d1)
{
if(root==null)
{
root=new Node(d1);
}
else if(root.data>d1)
{
root.left=insert_data(root.left,d1);
}
else
{
root.right=insert_data(root.right,d1);
}
return root;
}
import java.io.*;
class GFG
{
static Node root;
class Node
{
Node left,right;
int data;
Node(int d1)
{
data=d1;
left=right=null;
}
}
public void insert(int d1)
{
root=insert_data(root,d1);
}
public Node insert_data(Node root,int d1)
{
if(root==null)
{
root=new Node(d1);
}
else if(root.data>d1)
{
root.left=insert_data(root.left,d1);
}
else
{
root.right=insert_data(root.right,d1);
}
return root;
}
public void verticleSum(Node root,HashMap<Integer,Vector<Integer>> h1,int c)
{
if(root==null) return;
else
{
public static void main(String[] args)
{
GFG n1=new GFG();
n1.insert(99);
n1.insert(2);
n1.insert(3);
n1.insert(4);
n1.insert(0);
n1.insert(30);
n1.insert(15);
n1.insert(45);
n1.insert(101);
n1.insert(-1);
HashMap<Integer,Vector<Integer>> h1=new HashMap<Integer,Vector<Integer>>();
n1.verticleSum(root,h1,0);
TreeMap<Integer,Vector<Integer>> t1=new TreeMap<Integer,Vector<Integer>>(h1);
Set s1=t1.entrySet();
Iterator ir=s1.iterator();
while(ir.hasNext())
{
Map.Entry m1=(Map.Entry)ir.next();
System.out.println(m1.getKey()+" :"+m1.getValue());
}
}
}
{
if(root==null) return;
else
{
/* if we do this we can rearrange output
Vector<Integer> v1=h1.get(c);
if(v1==null) //to check new level
{
v1=new Vector<Integer>(); //creating new vector
v1.add(root.data); //addind element to vector
}
else
{
v1.add(root.data);
}
h1.put(c,v1);
*/
}
}
if(v1==null) //to check new level
{
v1=new Vector<Integer>(); //creating new vector
v1.add(root.data); //addind element to vector
}
else
{
v1.add(root.data);
}
h1.put(c,v1);
*/
}
}
{
GFG n1=new GFG();
n1.insert(99);
n1.insert(2);
n1.insert(3);
n1.insert(4);
n1.insert(0);
n1.insert(30);
n1.insert(15);
n1.insert(45);
n1.insert(101);
n1.insert(-1);
HashMap<Integer,Vector<Integer>> h1=new HashMap<Integer,Vector<Integer>>();
n1.verticleSum(root,h1,0);
TreeMap<Integer,Vector<Integer>> t1=new TreeMap<Integer,Vector<Integer>>(h1);
Set s1=t1.entrySet();
Iterator ir=s1.iterator();
while(ir.hasNext())
{
Map.Entry m1=(Map.Entry)ir.next();
System.out.println(m1.getKey()+" :"+m1.getValue());
}
}
}
19 check given tree is bst or not
boolean isBST(Node root,int min,int max)
{
if(root==null)
{
return true;
}
return(root.data>min && root.data<max && isBST(root.left,min,root.data) && isBST(root.right,root.data,max));
}
20.print element between integer k1 and k2
public void print(Node root,int d1,int d2)
{
if(root==null)
{
return;
}
else
{
if(root.data>=d1)
{
print(root.left,d1,d2);
}
if(root.data>=d1 && root.data<=d2)
{
System.out.print(root.data);
}
if(root.data<=d2)
{
print(root.right,d1,d2);
}
}
}
We can use level order traversal ….using queue.
21. Find the kth smallest element from binary tree.
int t=0;
public void print(Node root)
{
if(root!=null)
{
print(root.left);
t++;
if(t==7)
{
System.out.print(root.data);
}
print(root.right);
}
}
Comments
Post a Comment