Nodes at K distance

#1

My code is showing run time error for 3 test cases:\

#2

hey @ap8730390
try for this input
7
20 8 4 12 10 14 22
4 8 10 12 14 20 22
1
12 3
You are getting null pointer exception

#3

I dry ran my code but still was not able to find the error. Please help.

#4

import java.util.*; class Main{ static class Node{ int data; Node left; Node right; Node(int data){ this.data = data; left = right = null; } } static Node root = null; public static Node construct(int [] pre, int ps , int pe, int[]in, int is, int ie){ if(ps>pe){ return null; } if(ps == pe){ Node base = new Node(pre[ps]); return base; } Node nn = new Node(pre[ps]); int i = is; int count = 0; while(in[i]!=pre[ps]){ i++; count++; } nn.left = construct(pre,ps+1,ps+count,in,is,i-1); nn.right = construct(pre,ps+count+1,pe,in,i+1,ie); return nn; } public static void collectParents(HashMap<Node,Node> map){ LinkedList que = new LinkedList<>(); que.addLast(root); while(!que.isEmpty()){ Node rn = que.removeFirst(); if(rn== root){ map.put(rn,null); } if(rn.left != null){ map.put(rn.left,rn); que.addLast(rn.left); } if(rn.right != null){ map.put(rn.right,rn); que.addLast(rn.right); } } } public static Node findNode(Node node, int val){ if(node.data == val){ return node; } if(node.left!=null) { return findNode(node.left,val); } if(node.right!=null){ return findNode(node.right,val); } return null; } public static void printNodes(HashMap<Node,Node> map, int target, int k){ Node tar =findNode(root, target); HashSet set = new HashSet<>(); LinkedList que = new LinkedList<>(); que.addLast(tar); que.addLast(null); set.add(tar); int dist = 0; while(!que.isEmpty()){ if(dist == k){ if(que.isEmpty()){ System.out.println(“0”); break; } while(que.getFirst()!=null){ System.out.print(que.removeFirst().data+" “); } break; } while(que.getFirst()!=null){ Node rn = que.removeFirst(); if(rn.left != null && !set.contains(rn.left)){ que.addLast(rn.left); set.add(rn.left); } if(rn.right!=null && !set.contains(rn.right)){ que.addLast(rn.right); set.add(rn.right); } if(map.get(rn)!=null && !set.contains(map.get(rn))){ que.addLast(map.get(rn)); set.add(map.get(rn)); } } que.removeFirst(); dist++; if(que.size()>0){ que.addLast(null); } } } public static void solve(){ int n = scn.nextInt(); int [] pre = new int [n]; int [] in = new int [n]; for(int i = 0; i< n;i++){ pre[i]= scn.nextInt(); } for(int i = 0;i<n; i++){ in[i]= scn.nextInt(); } root = construct(pre,0,pre.length-1,in,0,in.length-1); } public static void display(Node node){ if(node == null) return; if(node.left!=null) System.out.print(node.left.data); System.out.print(” -> “+node.data+” <- "); if(node.right!=null) System.out.print(node.right.data); System.out.println(); display(node.left); display(node.right); } public static Scanner scn = new Scanner(System.in); public static void main(String [] args){ solve(); HashMap<Node, Node> map = new HashMap<>(); collectParents(map); // display(root); int t = scn.nextInt(); while(t–>0){ int target = scn.nextInt(); int k = scn.nextInt(); printNodes(map,target,k); System.out.println(); } } }

#5

Here is my code . Please tell me where is the error

#6

@ap8730390 7
20 8 4 12 10 14 22
4 8 10 12 14 20 22
1 10 1
Nothing is printing your code

#7

Wahi toh… I don’t know where the error lies. I think my logic is correct but why isn’t the code working?

#8

@ap8730390 ek barri tree Display krna sahi ho raha h ??

#9

Haan display to sahi ho raha hai

#10

@ap8730390 If the tree is well displayed
dry run your printNodes fun
it is wrong
correct code :

#11

Is my logic correct ?

#12

@ap8730390
Is my logic correct ?
Nope

#13

Arey … mera logic sahi tha bass if distance less than k waala case include karna bhool gaya tha. Thank you so much for the help