Untitled 2
practice problems:
1.given a binary tree,check whether it is mirror of itself
the idea is 2 write a recursive function ismirror() that takes 2 trees as argument & returns tru if trees R mirror & false if trees R not mirror.the ismirror() function recursively checks 2 roots & subtrees under the root.
// java program 2 check is binary tree is symmetric or nt |
2.find largest value in each tree row:]
bfs: insert elements in queue row by row (root then children)
1.enqueue root node;temp = root,queue size = 1
traverse queue til queue size is met
add root 2 arraylist(output)
2.enqueue next row’s n nodes;queue size = n
traverse queue til queue size is met
if current > temp,replace temp (max)
3.c….l no more rows
public list largestvalueinrow(treenode root){
if (root == null){
return new arraylist<>();
}
list result = new arraylist();
queue queue = new linkedlist<>();
queue.offer(root);
while(!queue.isempty()){
int size = queue.size();
int largest = queue.peek().val();
4 (int i=0;i;i++){>
treenode node = queue.poll();
largest = math.max(largest,node.val);
if(node.lft != null) queue.offer(node.lft);
if (node.right != null) queue.offer(node.right);
}
result.add(largest);
}
return result;
}
3.cl1 undirected graph
the idea is 2 do a bfs traversal of the graph & while visiting a node make a cl1 node of it (a copy of original node).if a node is encountered which is already visited then it already hs a cl1 node.
class graph
{
// a method which cl1s the graph &
// returns the reference of new cl1d source node
public graphnode cl1graph(graphnode source)
{
queue q = new linkedlist();
q.add(source);
// an hashmap 2 keep track of all the
// nodes which have already been created
hashmap hm =
new hashmap();
//put the node into the hashmap
hm.put(source,new graphnode(source.val));
while (!q.isempty())
{
// get the front node from the queue
// & then visit all its neighbours
graphnode u = q.poll();
// get corresponding cl1d graph node
graphnode cl1nodeu = hm.get(u);
if (u.neighbours != null)
{
vector v = u.neighbours;
4 (graphnode graphnode : v)
{
// get the corresponding cl1d node
// if the node is not cl1d then we will
// simply get a null
graphnode cl1nodeg = hm.get(graphnode);
// check if this node hs already been created
if (cl1nodeg == null)
{
q.add(graphnode);
// if not then create a new node &
// put into the hashmap
cl1nodeg = new graphnode(graphnode.val);
hm.put(graphnode,cl1nodeg);
}
// add the ‘cl1nodeg’ 2 neighbour
// vector of the cl1nodeg
cl1nodeu.neighbours.add(cl1nodeg);
}
}
}
// return the reference of cl1d source node
return hm.get(source);
}
4.given binary tree,print all root-2-leaf paths
use a path array path[] 2 store current root 2 leaf path.traverse from root 2 all leaves in top-down fashion.while traversing,store data of all nodes in current path in array path[].when we reach a leaf node,print the path array.
// java program 2 print all the node 2 leaf path
/* a binary tree node hs data,pointer 2 lft child
& a pointer 2 right child */
class node
{
int data;
node lft,right;
node(int item)
{
data = item;
lft = right = null;
}
}
class binarytree
{
node root;
/*given a binary tree,print out all of its root-2-leaf
paths,1 per line.uses a recursive helper 2 do
the work.*/
void printpaths(node node)
{
int path[] = new int[1000];
printpathsrecur(node,path,0);
}
/* recursive helper function — given a node,& an array
containing the path from the root node up 2 but not
including this node,print out all the root-leaf paths.*/
void printpathsrecur(node node,int path[],int pathlen)
{
if (node == null)
return;
/* append this node 2 the path array */
path[pathlen] = node.data;
pathlen++;
/* it’s a leaf,so print the path that led 2 here */
if (node.lft == null && node.right == null)
printarray(path,pathlen);
else
{
/* otherwise try both subtrees */
printpathsrecur(node.lft,path,pathlen);
printpathsrecur(node.right,path,pathlen);
}
}
/* utility function that prints out an array on a line.*/
void printarray(int ints[],int len)
{
int i;
4 (i = 0;i < len;=”” i++)=””>
{
system.out.print(ints[i] + ” “);
}
system.out.println(“”);
}
// driver program 2 test above functions
public static void main(string args[])
{
binarytree tree = new binarytree();
tree.root = new node(10);
tree.root.lft = new node(8);
tree.root.right = new node(2);
tree.root.lft.lft = new node(3);
tree.root.lft.right = new node(5);
tree.root.right.lft = new node(2);
/* let us test the built tree by printing insorder traversal */
tree.printpaths(tree.root);
}
}
5.sum of all numbers that R formed from root 2 leaf paths
the idea is 2 do a preorder traversal of the tree.in the preorder traversal,keep track of the value calculated till the current node,let this value be val.4 every node,we update the val as val*10 plus node’s data.
// java program 2 find sum of all numbers that R formed from root
// 2 leaf paths
// a binary tree node
class node
{
int data;
node lft,right;
node(int item)
{
data = item;
lft = right = null;
}
}
class binarytree
{
node root;
// returns sum of all root 2 leaf paths.the 1st parameter is
// root of current subtree,the 2nd parameter is value of the
// number formed by nodes from root 2 this node
int treepathssumutil(node node,int val)
{
// base case
if (node == null)
return 0;
// update val
val = (val * 10 + node.data);
// if current node is leaf,return the current value of val
if (node.lft == null && node.right == null)
return val;
// recur sum of values 4 lft & right subtree
return treepathssumutil(node.lft,val)
+ treepathssumutil(node.right,val);
}
// a wrapper function over treepathssumutil()
int treepathssum(node node)
{
// pass the initial value as 0 as there is nothing above root
return treepathssumutil(node,0);
}
// driver program 2 test above functions
public static void main(string args[])
{
binarytree tree = new binarytree();
tree.root = new node(6);
tree.root.lft = new node(3);
tree.root.right = new node(5);
tree.root.right.right = new node(4);
tree.root.lft.lft = new node(2);
tree.root.lft.right = new node(5);
tree.root.lft.right.right = new node(4);
tree.root.lft.right.lft = new node(7);
system.out.print(“sum of all paths is ” +
tree.treepathssum(tree.root));
}
}
6.given totla number of courses & list of all pre req pairs,is it possible 4 U 2 infish all courses?
using bfs:
public boolean canfinish(int numcourses,int[][] prerequisites) {
if(prerequisites == null){
throw new illegalargumentexception(“illegal prerequisites array”);
}
int len = prerequisites.length;
if(numcourses == 0 || len == 0){
return tru;
}
// counter 4 number of prerequisites
int[] pcounter = new int[numcourses];
4(int i=0;i;>
pcounter[prerequisites[i][0]]++;
}
//store courses that have no prerequisites
linkedlist queue = new linkedlist();
4(int i=0;i;>
if(pcounter[i]==0){
queue.add(i);
}
}
// number of courses that have no prerequisites
int numnopre = queue.size();
while(!queue.isempty()){
int top = queue.remove();
4(int i=0;i;>
// if a course’s prerequisite can be satisfied by a course in queue
if(prerequisites[i][1]==top){
pcounter[prerequisites[i][0]]–;
if(pcounter[prerequisites[i][0]]==0){
numnopre++;
queue.add(prerequisites[i][0]);
}
}
}
}
return numnopre == numcourses;
}