Binary Tree.txt

SOLUTIONS OF THESE QUESTIONS ARE EITHER ON GFG OR ON LEETCODE.
---------------------------------------BINARY TREE-----------------------------------------

1.Level Order Traversal
private List<List<Integer>> levelArrayList(List<List<Integer>> list, TreeNode node, int level) {
		if (node == null) {
			return list;
		}

			if (list.size() == level) {
				list.add(new ArrayList<>());
			}
			list.get(level).add(node.val);
		
		list = levelArrayList(list, node.left, level + 1);
		list = levelArrayList(list, node.right, level + 1);

		return list;
	}
#In Reverse Level Order Traversal  just use Collections.reverse(list); and then return
->
void reverseLevelOrder(Node node)
    {
        Stack<Node> S = new Stack();
        Queue<Node> Q = new LinkedList();
        Q.add(node);
  
        // Do something like normal level order traversal order.Following
        // are the differences with normal level order traversal
        // 1) Instead of printing a node, we push the node to stack
        // 2) Right subtree is visited before left subtree
        while (Q.isEmpty() == false)
        {
            /* Dequeue node and make it root */
            node = Q.peek();
            Q.remove();
            S.push(node);
  
            /* Enqueue right child */
            if (node.right != null)
                // NOTE: RIGHT CHILD IS ENQUEUED BEFORE LEFT
                Q.add(node.right);
                 
            /* Enqueue left child */
            if (node.left != null)
                Q.add(node.left);
        }
  
        // Now pop all items from stack one by one and print them
        while (S.empty() == false)
        {
            node = S.peek();
            System.out.print(node.data + " ");
            S.pop();
        }
    }
-----------------------------------------------------------------------------------
2. Height of a Binary Tree
 public int maxDepth(TreeNode node) {
	           if (node == null) {
		return 0;    //if zero based indexing then we would have returned -1
                            }

		int lh = maxDepth(node.left);
		int rh = maxDepth(node.right);
		return Math.max(lh, rh) + 1;
                       }
-----------------------------------------------------------------------------------
3. Min Depth of Binary tree
public int minDepth(TreeNode root) {
        if(root==null){
          return 0;
        }
        int lh=minDepth(root.left);
        int rh=minDepth(root.right);
        
        if(lh==0){  //if right skewed tree
            return rh+1;
        }
        if(rh==0){  //if left skewed tree
            return lh+1;
        }
        return Math.min(lh,rh)+1;   
    }
-----------------------------------------------------------------------------------	
4. Diameter of a Binary Tree
 private class DiaPair {
		int h = -1;
		int d = 0;
	}

	private DiaPair Diameter(TreeNode node) {
		if (node == null) {
			return new DiaPair();
		}

		DiaPair ldp = Diameter(node.left);
		DiaPair rdp = Diameter(node.right);

		DiaPair sdp = new DiaPair();

		int ld = ldp.d;
		int rd = rdp.d;
		int sp = ldp.h + rdp.h + 2;

		sdp.h = Math.max(ldp.h, rdp.h) + 1;
		sdp.d = Math.max(sp, Math.max(ld, rd));

		return sdp;
	}

-> 
private int height(TreeNode node, int[] diameter) {
        if (node == null) {
            return 0;
        }
        int lh = height(node.left, diameter);
        int rh = height(node.right, diameter);
        diameter[0] = Math.max(diameter[0], lh + rh);
        return 1 + Math.max(lh, rh);
    }
-----------------------------------------------------------------------------------	
5. Invert the Tree
public TreeNode invertTree(TreeNode node) {
        if(node==null){
            return null;
        }
        
        TreeNode l=node.left;
        TreeNode r=node.right;

        node.left=r;
        node.right=l;        
        
        node.left=invertTree(node.left);
        node.right=invertTree(node.right);
        return node;
    }
-----------------------------------------------------------------------------------	
6. Right Side View of Binary Tree

public List<Integer> rightSideView(TreeNode root) {
        List<Integer>ans=new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null){
            return ans;
               }
        
		TreeNode nn = root;
		queue.add(nn);
		queue.add(null);
		while (!queue.isEmpty()) {
			TreeNode rn = queue.remove();
			if (rn == null) {
				if (queue.isEmpty()) {
					break;
				}
				queue.add(null);
				continue;
			}
			if (queue.peek() == null) {
				ans.add(rn.val);
			}

			if (rn.left != null) {
				queue.add(rn.left);
			}
			if (rn.right != null) {
				queue.add(rn.right);
			}
		}
        return ans;
    }

-> Recursive way easier 
public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    }
    
    public void rightView(TreeNode curr, List<Integer> result, int currDepth){
        if(curr == null){
            return;
        }
        if(currDepth == result.size()){
            result.add(curr.val);
        }
        
        rightView(curr.right, result, currDepth + 1);
        rightView(curr.left, result, currDepth + 1);   
    }
-----------------------------------------------------------------------------------	
7. Left Side view of Binary Tree
public List<Integer> rightSideView(TreeNode root) {
        List<Integer>ans=new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null){
            return ans;
               }
        
		TreeNode nn = root;
		queue.add(nn);
		queue.add(null);
		ans.add(root.val);
		while (!queue.isEmpty()) {
			TreeNode rn = queue.remove();
			if (rn == null) {
				if (queue.isEmpty()) {
					break;
				}
				ans.add(queue.peek().val);
				queue.add(null);
				continue;
			}
			
			if (rn.left != null) {
				queue.add(rn.left);
			}
			if (rn.right != null) {
				queue.add(rn.right);
			}
		}
        return ans;
    }
-----------------------------------------------------------------------------------	
8. Vertical display of Binary Tree Leetcode-987
private class VDPair implements Comparable<VDPair> {
		int val;
		int vlevel;
		int hlevel;

		VDPair(int val, int vlevel, int hlevel) {
			this.val = val;
			this.vlevel = vlevel;
			this.hlevel = hlevel;
		}

		@Override
		public String toString() {
			return val + "";
		}

		@Override
		public int compareTo(VDPair other) {
            if(this.hlevel==other.hlevel)return this.val-other.val;
			return this.hlevel - other.hlevel;
		}
	}
    public List<List<Integer>> VerticalDisplay(TreeNode root) {
		HashMap<Integer, ArrayList<VDPair>> map = new HashMap<>();
		VerticalDisplay(root, map, 0, 0);

        List<List<Integer>>ans=new ArrayList<>();
		List<Integer> allkeys = new ArrayList<>(map.keySet());
		Collections.sort(allkeys);
		for (Integer key : allkeys) {
			List<VDPair> list = map.get(key);
			Collections.sort(list);  // horizontal sorting so that elements will be sorted according to their level
            List<Integer>res=new ArrayList<>();
            for(int i=0;i<list.size();i++)
                res.add(list.get(i).val);
            ans.add(res);
		}
        return ans;
	}
    private void VerticalDisplay(TreeNode node, HashMap<Integer, ArrayList<VDPair>> map, int vlevel, int hlevel) {
		if (node == null) {
			return;
		}
		if (!map.containsKey(vlevel)) {
			ArrayList<VDPair> list = new ArrayList<>();
			map.put(vlevel, list);
		}

		VDPair np = new VDPair(node.val, vlevel, hlevel);
		map.get(vlevel).add(np);

		VerticalDisplay(node.left, map, vlevel - 1, hlevel + 1);
		VerticalDisplay(node.right, map, vlevel + 1, hlevel + 1);
	}

# For Diagonal Traversal , just put (hlevel-vlevel) in map instead of vlevel only.
#For Top view just put FIRST element of vertical order traversal  in ANS Arraylist.
#For Bottom view just put LAST element of vertical order traversal  in ANS Arraylist.

//Top View
->
//Function to return a list of nodes visible from the top view 
    //from left to right in Binary Tree.
    static ArrayList<Integer> topView(Node root)
    {
        ArrayList<Integer> ans = new ArrayList<>(); 
        if(root == null) return ans;
        Map<Integer, Integer> map = new TreeMap<>();
        Queue<Pair> q = new LinkedList<Pair>();
        q.add(new Pair(root, 0)); 
        while(!q.isEmpty()) {
            Pair it = q.remove();
            int hd = it.hd; 
            Node temp = it.node; 
            if(map.get(hd) == null) map.put(hd, temp.data); 
            if(temp.left != null) {
                
                q.add(new Pair(temp.left, hd - 1)); 
            }
            if(temp.right != null) {
                
                q.add(new Pair(temp.right, hd + 1)); 
            }
        }
    
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            ans.add(entry.getValue()); 
        }
        return ans; 
    }

-> Bottom view

//Function to return a list containing the bottom view of the given tree.
    public ArrayList <Integer> bottomView(Node root)
    {
        ArrayList<Integer> ans = new ArrayList<>(); 
        if(root == null) return ans;
        Map<Integer, Integer> map = new TreeMap<>();
        Queue<Node> q = new LinkedList<Node>();
        root.hd = 0;  //hd = the division line tha axis ( left side it is negative, right side it is positive, root side its 0)
        q.add(root); 
        while(!q.isEmpty()) {
            Node temp = q.remove();
            int hd = temp.hd; 
            map.put(hd, temp.data); // at last updated hd->(value) it will get the bottom view node
            if(temp.left != null) {
                temp.left.hd = hd - 1; 
                q.add(temp.left); 
            }
            if(temp.right != null) {
                temp.right.hd = hd + 1; 
                q.add(temp.right); 
            }
        }
        
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            ans.add(entry.getValue()); 
        }
        return ans;    
    }

-----------------------------------------------------------------------------------	
9. Lowest Common Ancestor -O(N)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        
        if(root.val==p.val||root.val==q.val){
            return root;
        }
        TreeNode leftlca=lowestCommonAncestor(root.left,p,q);
        TreeNode rightlca=lowestCommonAncestor(root.right,p,q);
    
    
        if(leftlca!=null&&rightlca!=null){
            return root;
        }
        if(leftlca!=null){
            return leftlca;
        }
        return rightlca;
    }
-----------------------------------------------------------------------------------	
10. ZigZagLevelOrder Traversal O(n)S(n)
 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        LinkedList<TreeNode> PrimaryS = new LinkedList<>();
		LinkedList<TreeNode> helperS = new LinkedList<>();

        List<List<Integer>>ans=new ArrayList<>();
        if(root==null)return ans;
        
		TreeNode nn = root;
		PrimaryS.addFirst(nn);
		int count = 0;
        List<Integer>res=new ArrayList<>();
		while (!PrimaryS.isEmpty()) {
			TreeNode rm = PrimaryS.removeFirst();
			if (rm != null) {
				    res.add(rm.val);
				if (count % 2 == 0) {
					helperS.addFirst(rm.left);
					helperS.addFirst(rm.right);
				} else {
					helperS.addFirst(rm.right);
					helperS.addFirst(rm.left);
				}
			}

			if (PrimaryS.isEmpty()) {
				count++;
                if(res.size()>0)
				  ans.add(res);
                
                res=new ArrayList<>();
				PrimaryS = helperS;
				helperS = new LinkedList<>();
			}
		}
        return ans;
    }

-> Using one Queue only
 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
        
        if(root == null) return wrapList;
        
        queue.offer(root);
        boolean flag = true;   //for changing direction 
        while(!queue.isEmpty()){
            int levelNum = queue.size();
            List<Integer> subList = new ArrayList<Integer>(levelNum);
            for(int i=0; i<levelNum; i++) {
                int index = i;
                if(queue.peek().left != null) queue.offer(queue.peek().left);
                if(queue.peek().right != null) queue.offer(queue.peek().right);
                if(flag == true) subList.add(queue.poll().val);
                else subList.add(0, queue.poll().val);
            }
            flag = !flag; 
            wrapList.add(subList);
        }
        return wrapList;
    }
-----------------------------------------------------------------------------------	
11. Balanced Binary Tree
private class Balpair {
		int h = -1;
		boolean b = true;
	}

	private Balpair isbalanced(TreeNode node) {
		if (node == null) {
			return new Balpair();
		}
		Balpair lbp = isbalanced(node.left);
		Balpair rbp = isbalanced(node.right);

		Balpair sbp = new Balpair();

		boolean lb = lbp.b;
		boolean rb = rbp.b;
		int blf = lbp.h - rbp.h;

		sbp.b = (lb && rb && (blf == -1 || blf == 0 || blf == 1));
		sbp.h = Math.max(lbp.h, rbp.h) + 1;

		return sbp;
	}
-----------------------------------------------------------------------------------	
12. Largest SubTree Sum
private class SubtreePair {
		int entireSum = 0;
		int maxSumtillnow = Integer.MIN_VALUE;
	}

	private SubtreePair MaxSubtreeSum1(Node node) {
		if (node == null) {
			return new SubtreePair();
		}

		SubtreePair lp = MaxSubtreeSum1(node.left);
		SubtreePair rp = MaxSubtreeSum1(node.right);

		SubtreePair sp = new SubtreePair();

		int lesum = lp.entireSum;
		int resum = rp.entireSum;

		sp.entireSum = lesum + resum + node.data;
		sp.maxSumtillnow = Math.max(sp.entireSum, Math.max(lp.maxSumtillnow, rp.maxSumtillnow));
		return sp;
	}
--->
static int ms=Integer.MIN_VALUE;
    static int msn=0;
    public static int NodeWithMaxSubtreeSum(Node node){
        int sum=0;
        for(Node child:node.children){
            sum+=NodeWithMaxSubtreeSum(child);
        }
        sum+=node.data;
        if(sum>ms){
            ms=sum;
            msn=node.data;
        }
        return sum;
    }
-----------------------------------------------------------------------------------	
13. Contruct Binary Tree from preorder and inorder traversal
# without traversing everytime you can just add every element of inorder in a hashmap and get it in constant time

private TreeNode constructPreIn(int[] pre, int plo, int phi, int[] in, int ilo, int ihi) {
		if (plo > phi || ilo > ihi) {
			return null;
		}

		TreeNode nn = new TreeNode();
		nn.val = pre[plo];
		int si = -1;   //can use hashmap to get this idx in constant time.
		for (int i = ilo; i <= ihi; i++) {
			if (in[i] == nn.val) {
				si = i;
				break;
			}
		}
		int nel = si - ilo;
		nn.left = constructPreIn(pre, plo + 1, plo + nel, in, ilo, si - 1);
		nn.right = constructPreIn(pre, plo + nel + 1, phi, in, si + 1, ihi);
		return nn;
	}
-> Using postorder and inorder traversal
private Node constructPostIn(int[] post, int plo, int phi, int[] in, int ilo, int ihi) {
		if (plo > phi || ilo > ihi) {
			return null;
		}

		Node nn = new Node();
		nn.data = post[phi];
		int si = -1;
		for (int i = ilo; i <= ihi; i++) {
			if (in[i] == nn.data) {
				si = i;
				break;
			}
		}
		int nel = si - ilo;
		nn.left = constructPostIn(post, plo, plo + nel - 1, in, ilo, si - 1);
		nn.right = constructPostIn(post, plo + nel, phi - 1, in, si + 1, ihi);
		return nn;
	}
-----------------------------------------------------------------------------------	
14. Symmetric Tree
 public boolean isSymmetric(TreeNode left,TreeNode right){
        if(left==null|right==null){
            return (left==right);
        }
        
        if(left.val!=right.val)
            return false;
        //checking for folding (concealing)
        return isSymmetric(left.left,right.right) && isSymmetric(left.right,right.left);
    }
-----------------------------------------------------------------------------------	
15. Check if 2 trees are mirror of each other
 boolean areMirror(Node a, Node b)
    {
        if (a == null && b == null)
            return true;
 
        if (a == null || b == null)
            return false;

        return a.data == b.data && areMirror(a.left, b.right) && areMirror(a.right, b.left);
    }
-----------------------------------------------------------------------------------
16. Preorder (Recursively & Iteratively)
Recursively->
private void preorder(Node node) {
		if (node == null) {
			return;
		}

		System.out.print(node.data + " ");
		preorder(node.left);
		preorder(node.right);
	}
Iteratively->
 public List<Integer> preorderTraversal(TreeNode root) {
        Stack<Pair> st = new Stack<>();
        List<Integer>ans=new ArrayList<>();
        if(root==null)return ans;
        
		Pair np = new Pair();
		np.n = root;
		st.push(np);
		while (!st.isEmpty()) {
			Pair tp = st.peek();
			if (!tp.sd) {
				ans.add(tp.n.val);
				tp.sd = true;
			} else if (!tp.ld) {
				Pair nlp = new Pair();
				nlp.n = tp.n.left;
				if (nlp.n != null) {
					st.push(nlp);
				}
				tp.ld = true;
			} else if (!tp.rd) {
				Pair nrp = new Pair();
				nrp.n = tp.n.right;
				if (nrp.n != null) {
					st.push(nrp);
				}
				tp.rd = true;
			} else
				st.pop();
		}
        return ans;
    }
    	private class Pair {
		TreeNode n;
		boolean sd;
		boolean ld;
		boolean rd;
	}
-----------------------------------------------------------------------------------	
17. All Traversals (Iteratively)
private void AllTraversals(Node root) {
		Stack<TPair> st = new Stack<>();

		TPair np = new TPair(root, 1);
		st.push(np);
		String pre = "";
		String in = "";
		String pos = "";
		while (!st.isEmpty()) {
			TPair top = st.peek();
			if (top.state == 1) { // pre s++ left
				pre += top.n.data + " ";
				top.state++;
				if (top.n.left != null) {
					TPair nlp = new TPair(top.n.left, 1);
					st.push(nlp);
				}
			} else if (top.state == 2) { // in s++ right
				in += top.n.data + " ";
				top.state++;
				if (top.n.right != null) {
					TPair nrp = new TPair(top.n.right, 1);
					st.push(nrp);
				}
			} else { // pos pop()
				pos += top.n.data + " ";
				st.pop();
			}
		}
		System.out.println("pre-> " + pre);
		System.out.println("in-> " + in);
		System.out.println("pos-> " + pos);
	}

	class TPair {
		int state;
		Node n;

		TPair(Node nn, int s) {
			n = nn;
			state = s;
		}
	}
-----------------------------------------------------------------------------------	
18. Boundary Traversal
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer>list=new ArrayList<>();
        if(root==null){
            return list;
        }
	    list.add(root.val);
	    left(root.left,list);
	    leaf(root,list);
	    right(root.right,list);
	    return list;
	}
	
	void left(TreeNode node,List<Integer>list){
	    if(node==null)
	        return;
	   if(node.left!=null){
	       list.add(node.val);
	       left(node.left,list);
	   }else if(node.right!=null){
	       list.add(node.val);
	       left(node.right,list);
	   }     
	}
	void leaf(TreeNode node,List<Integer>list){
	    if(node==null)
	        return;
	       leaf(node.left,list);
	   if(node.left==null&&node.right==null){
	       list.add(node.val);
	   }
	    leaf(node.right,list);
	}
	void right(TreeNode node,List<Integer>list){
	    if(node==null)
	        return;
	   if(node.right!=null){
	      right(node.right,list);
	      list.add(node.val);
	   }else if(node.left!=null){
	       right(node.left,list);     
	       list.add(node.val);
	   }     
	}
-----------------------------------------------------------------------------------	
19. Root-to-leaf has pathSum to targeted val
 public boolean hasPathSum(TreeNode node, int targetSum) {
        if(node==null){
            return false;
        }
        if(node.left==null && node.right==null && targetSum-node.val==0){
            return true;
        }
        boolean lp=hasPathSum(node.left,targetSum-node.val);
        boolean rp=hasPathSum(node.right,targetSum-node.val);
        
        return lp||rp;  
    }
-----------------------------------------------------------------------------------	
20. Check for Sum Tree
pair checkSumTree(Node node){
	    if(node==null){
	        return new pair();
	    }
	    
	    pair lp=checkSumTree(node.left);
	    pair rp=checkSumTree(node.right);
	    
	    pair sp=new pair();
	    
	    
	    if(node.data==lp.entiresum+rp.entiresum && lp.b && rp.b){
	        sp.b=true;
	    }else if(node.left==null&&node.right==null){
	        sp.b=true;
	    }else 
	        sp.b=false;
	    
	    sp.entiresum=lp.entiresum+rp.entiresum+node.data;
	    
	    return sp;
	    
	}
	
	class pair{
	    int entiresum=0;
	    boolean b=true;
	}
-----------------------------------------------------------------------------------	
21. Convert Binary Tree into SumTree
 public int SumTreeConvert(Node node){
        if(node==null){
            return 0;
        }
        
        int lsum=SumTreeConvert(node.left);
        int rsum=SumTreeConvert(node.right);
        
        int temp=node.data;
        node.data=lsum+rsum;
        
        return temp+node.data;
    }
-----------------------------------------------------------------------------------
22. Leaf at same level
boolean leafSameLevel(Node node,int level,Set<Integer>set){
        if(node==null){
            return true;
        }
        if(node.left==null&&node.right==null){
            set.add(level);
            if(set.size()>1){
                return false;
            }else 
                return true;
        }
        boolean l=leafSameLevel(node.left,level+1,set);
        boolean r=leafSameLevel(node.right,level+1,set);

        return l&&r;
    }
-----------------------------------------------------------------------------------	
23. Sum of the Longest Bloodline of a Tree (Sum of nodes on the longest path from root to leaf node)
 public void SumoflongestR2L(Node node,int level,int sum,int[]arr){
        if(node==null){
            return;
        }
        
        if(node.left==null&&node.right==null){
            if(level>arr[0]){
                arr[0]=level;
                arr[1]=sum+node.data;
            }else if(level==arr[0]){
                arr[1]=Math.max(arr[1],sum+node.data);
            }
            return;
        }
        
        SumoflongestR2L(node.left,level+1,sum+node.data,arr);
        SumoflongestR2L(node.right,level+1,sum+node.data,arr);
    }
-----------------------------------------------------------------------------------	
24. Min distance between two given nodes of a Binary Tree.

Root to node distance->
private static int findDistance(Node1 root, int n) {

if (root == null)
return -1;

if (root.value == n)
return 0;
int left = findDistance(root.left, n);
int right = findDistance(root.right, n);

if(left==-1 && right==-1)
return -1;
return 1+Math.max(left, right);
}

int findDist(Node root, int a, int b) {
        int item=lca(root,a,b);
        return root2node(root,a)+root2node(root,b)-2*(root2node(root,item));
    }
    int root2node(Node node,int val){
        if(node==null){
            return -1;
        }
        int dis=-1;
       if((node.data==val)||(dis=root2node(node.left,val))>=0||(dis=root2node(node.right,val))>=0)
        return dis+1;
        
        return dis; //if not found yet;
    }
    
    int lca(Node node,int a,int b){
        if(node==null){
            return -1;
        }
        if(node.data==a||node.data==b){
            return node.data;
        }
        
        int l=lca(node.left,a,b);
        int r=lca(node.right,a,b);
        
        if(l!=-1&&r!=-1){
            return node.data;
        }
        if(l!=-1){
            return l;
        }
        return r;
    }
-----------------------------------------------------------------------------------
25. All Nodes Distance K in Binary Tree (Leetcode->863.)

   //DryRun for best understanding 
    public List<Integer> distanceK(TreeNode node, TreeNode target, int k) {
        List<Integer>ans=new ArrayList<>();
        if(node==null)return ans;
      //it will collect the path from target to root.  
        ArrayList<TreeNode>path=new ArrayList<>();
	    node2rootpath(node,target.val,path);
	    for(int i=0;i<path.size();i++){
		CollectKlevelDown(path.get(i),k-i,i==0?null:path.get(i-1),ans);  
            //sending a blocker so that //elements which are already collected in ans do not get //collected again due to same level.
	    }
        return ans;
    }  
    
public boolean node2rootpath(TreeNode node,int item,ArrayList<TreeNode>list){
	if(node==null){
	 return false;
	}

	if(node.val==item){
		list.add(node);
		return true;
	}
	boolean lc=node2rootpath(node.left,item,list);
	if(lc){
		list.add(node);
		return true;
	}

	boolean rc=node2rootpath(node.right,item,list);
	if(rc){
		list.add(node);
		return true;
	}

	return false;
}
    public void CollectKlevelDown(TreeNode node,int k,TreeNode blocker,List<Integer>ans){
	if(node==null||k<0||node==blocker){
	  return;
	}

	if(k==0){
		ans.add(node.val);
	}
	CollectKlevelDown(node.left,k-1,blocker,ans);
	CollectKlevelDown(node.right,k-1,blocker,ans);
}

-> Striver explaination

* Mark each node to its parent to traverse upwards
* We will do a BFS traversal starting from the target node
* As long as we have not seen our node previously, Traverse up, left, right until reached Kth distance
* when reached Kth distance, break out of BFS loop and remaining node's values in our queue is our result

->
 private void markParents(TreeNode root, Map<TreeNode, TreeNode> parent_track, TreeNode target) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()) { 
            TreeNode current = queue.poll(); 
            if(current.left != null) {
                parent_track.put(current.left, current);
                queue.offer(current.left);
            }
            if(current.right != null) {
                parent_track.put(current.right, current);
                queue.offer(current.right);
            }
        }
    }
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        Map<TreeNode, TreeNode> parent_track = new HashMap<>();
        markParents(root, parent_track, root); 
        Map<TreeNode, Boolean> visited = new HashMap<>(); 
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(target);
        visited.put(target, true);
        int curr_level = 0;
        while(!queue.isEmpty()) { /*Second BFS to go upto K level from target node and using our hashtable info*/
            int size = queue.size();
            if(curr_level == k) break;
            curr_level++;
            for(int i=0; i<size; i++) {
                TreeNode current = queue.poll(); 
                if(current.left != null && visited.get(current.left) == null) {
                    queue.offer(current.left);
                    visited.put(current.left, true);
                }
                if(current.right != null && visited.get(current.right) == null ) {
                    queue.offer(current.right);
                    visited.put(current.right, true);
                }
                if(parent_track.get(current) != null && visited.get(parent_track.get(current)) == null) {
                    queue.offer(parent_track.get(current));
                    visited.put(parent_track.get(current), true);
                }
            }
        }
        List<Integer> result = new ArrayList<>(); 
        while(!queue.isEmpty()) {
            TreeNode current = queue.poll(); 
            result.add(current.val);
        }
        return result;
    }
-----------------------------------------------------------------------------------
26. Flip Equivalent Binary Trees (Isomorphic Trees)
  public boolean flipEquiv(TreeNode n1, TreeNode n2) {
        if(n1==null||n2==null){
            return n1==n2;
        }
        if(n1.val!=n2.val)return false;
        
        boolean o1=flipEquiv(n1.left,n2.left);
        boolean o2=flipEquiv(n1.right,n2.right);
        boolean o3=flipEquiv(n1.left,n2.right);
        boolean o4=flipEquiv(n1.right,n2.left);
        
        return (o1&&o2)||(o3&&o4);
    }
-----------------------------------------------------------------------------------
27. Print all K Sum paths
 static Vector<Integer> path = new Vector<Integer>();
// This function prints all paths that have sum k 
static void printKPathUtil(Node root, int k) 
{ 
     if (root == null) 
        return; 
  
    path.add(root.data); 
  
    printKPathUtil(root.left, k); 
    printKPathUtil(root.right, k); 
  
    int f = 0; 
    for (int j = path.size() - 1; j >= 0; j--) 
    { 
        f += path.get(j); 
  
        // If path sum is k, print the path but do not break it because it might happen that we get another path
        if (f == k) 
            printVector(path, j); 
    } 
  
    // Remove the current element from the path 
    path.remove(path.size() - 1); 
} 

-> Another Approach


 int total=0;
 public int sumK(Node root,int k)
   {
       if(root==null)return 0;
       Map<Integer,Integer>map=new HashMap<>();
       map.put(0,1);
       
      solve(root,k,0,map);
      return total;
}    
void solve(Node root,int target,int currSum,Map<Integer,Integer>map){
   if(root==null)return;
   currSum+=root.data;
   if(map.containsKey(currSum-target)){
       total+=map.get(currSum-target);
   }
   map.put(currSum,map.getOrDefault(currSum,0)+1);
   solve(root.left,target,currSum,map);
   solve(root.right,target,currSum,map);
   map.put(currSum,map.get(currSum)-1);
   return;
} 
----------------------------------------------------------------------------------
28.  Find if tree contains duplicate subtrees of size two or more
int DuplicateSubtrees(Node root) {
    HashMap<String,Integer>map=new HashMap<>();
       checkforDuplicates(root,map);
       for(String key:map.keySet()){
           if(map.get(key)>=2)
                return 1;
       }
       return 0;
    }
    
    String checkforDuplicates(Node node,HashMap<String,Integer>map){
        if(node==null){
            return "$";
        }
        String str="";
        if(node.left==null && node.right==null){
            str+=node.data;
            return str;
        }
        
        str+=node.data;
        str+=checkforDuplicates(node.left,map);
        str+=checkforDuplicates(node.right,map);
        
        map.put(str,map.getOrDefault(str,0)+1);  //this map contains all subtrees except leaf ones
        return str;
    }
-----------------------------------------------------------------------------------
29.  Duplicate Subtrees
 // O(n) O(n)
// we can do with only 1 hashmap also here.
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
	List<TreeNode> ans = new ArrayList<>();
	HashMap<String, Integer> serial2Id = new HashMap<>();
	HashMap<Integer, Integer> freq = new HashMap<>();
    int[]currId=new int[]{1};
	findDuplicateSubtrees2(root, serial2Id, freq, ans,currId);
	return ans;
   }

public int findDuplicateSubtrees2(TreeNode root, HashMap<String, Integer> serial2Id, HashMap<Integer, Integer> map,List<TreeNode> ans,int[]currId) {

	if (root == null)
		return 0;

	int left = findDuplicateSubtrees2(root.left, serial2Id, map, ans,currId);
	int right = findDuplicateSubtrees2(root.right, serial2Id, map, ans,currId);
	StringBuilder sb = new StringBuilder();
	sb.append(root.val);
	sb.append("_");
	sb.append(left);
	sb.append("_");
	sb.append(right);

	String serial = sb.toString();
	int id = serial2Id.getOrDefault(serial, currId[0]++);
	int freq = map.getOrDefault(id, 0);
	serial2Id.put(serial, id);

	if (freq == 1) {
		ans.add(root);
		map.put(id, 2);
	} else if (freq == 0)
		map.put(id, 1);

	return id;
}
-----------------------------------------------------------------------------------
30. Subtree of Another Tree
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
     if(root==null){
         return false;
     }else if(isSameTree(root,subRoot)){
         return true;
     }else 
        return (isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot)); 
    }

    public boolean isSameTree(TreeNode root,TreeNode subRoot){
        if(root==null||subRoot==null){
            return root==subRoot;
        }
        
        if(root.val==subRoot.val){
            return isSameTree(root.left,subRoot.left)&&isSameTree(root.right,subRoot.right);
        }
        return false;
    }

#) Optimised O(N) S(N) Method
-> Firstly we collect inorder and preorder traversals of both the trees in an arraylist.
-> We know that inorder and preorder uniquely defines a binary tree that's why we are using this.
-> Now we just check that inorder of substree is a subarray of big tree and same with preorder.
-> This can be checked using "KMP" for optimised solution.
-> It may happen that even after having both the subarray still we can say that small tree is not a subtree of Big.
(        Tree1
          x 
        /    \
      a       b
     /        
    c         


        Tree2
          x 
        /    \
      a       b
     /         \
    c            d
)
-> So to avoid this condition we just return any character say '$' when node becomes null while collecting inorder or preorder.
-> So to become a subtree both of its inorder and preorder should be subarrays of Big tree.
-----------------------------------------------------------------------------------
31.  Construct a Binary tree from String
     int start=0;
    public TreeNode str2tree(String s) {
        if(s.length()==0||s==null){
            return null;
        }
        return constructTreeFString(s);
    }

    public TreeNode constructTreeFString(String str){
        if(start>=str.length()){
            return null;
        }
        boolean neg=false;
        if(str.charAt(start)=='-'){
            neg=true;
            start++;
        }
        int num=0;
        while(start<str.length()&&Character.isDigit(str.charAt(start))){
            int digit=Character.getNumericValue(str.charAt(start));
            num=num*10+digit;
            start++;
        }

        if(neg){
            num=-num;
        }
        TreeNode root=new TreeNode(num);

        if(start>=str.length())
            return root;

        if(start<str.length()&&str.charAt(start)=='('){
            start++;
            root.left=constructTreeFString(str);
        }

        if(start<str.length()&&str.charAt(start)==')'){
            start++;
            return root;
        }

        if(start<str.length()&&str.charAt(start)=='('){
            start++;
            root.right=constructTreeFString(str);
        }

        if(start<str.length()&&str.charAt(start)==')'){
            start++;
            return root;
        }
        return root;
    }

-----------------------------------------------------------------------------------
32. Convert Binary Tree to LinkedList
 Node headLinkedList;
  Node prev;
    Node bToDLL(Node root)
    {
        B2Dll(root);
        return headLinkedList;
    }
    void B2Dll(Node node){
           if(node==null){
            return;
        }	
        bToDLL(node.left);
        if(prev==null){
            headLinkedList=prev=node;
        }else{
            node.left=prev;   //left ->previous
            prev.right=node;  //right->next
            prev=node;
        }
        bToDLL(node.right);
    }
-----------------------------------------------------------------------------------
33. Flatten Binary Tree to linkedList
w/Morris Traversal->https://i.imgur.com/sqnrz9m.gif

*** Preorder traversal should be same.


public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode runner = curr.left;
                while (runner.right != null) runner = runner.right;
                runner.right = curr.right;
                curr.right = curr.left;
                curr.left = null;
            }
            curr = curr.right;
        }
    }
w/Recursion
 TreeNode head = null;
    public void flatten(TreeNode root) {
        if (root != null) revPreOrder(root);
    }
    private void revPreOrder(TreeNode node) {
        if (node.right != null) revPreOrder(node.right);
        if (node.left != null) revPreOrder(node.left);
        node.left = null;
        node.right = head;
        head = node;
    }
-----------------------------------------------------------------------------------
34. Binary Tree Maximum path Sum
 public int maxPathSum(TreeNode root) {
        int[]result=new int[]{Integer.MIN_VALUE};
        MaxpathSum(root,result);   
        return result[0];
    }
    int MaxpathSum(TreeNode node,int[]result){
        if(node==null){
            return 0;
        }
        int left=MaxpathSum(node.left,result);
        int right=MaxpathSum(node.right,result);
    
        //case1: when path passes through current root node.
        int ms_straight=Math.max(node.val,Math.max(left,right)+node.val); 
       //case2: This covers case 1 and case when path passes through left to root to right.
        int mx_case=Math.max(ms_straight,left+right+node.val);
        result[0]=Math.max(mx_case,result[0]);
        
        return ms_straight;
    }

-> Striver's explaination
-> At each node we are making the curve path ( finding left_max_sum_path and right_max_sum_path) then 
 max =Math.max(max, left_sum + right_sum + node.data) and we are sending the max sum path at each node like 
 return node.data +Math.max(left_sum,right_sum); (since for the parent child can give the max path covering node + either left path or right path)

 public int maxPathSum(TreeNode root) {
        int[] max =new int[1];
        max[0]=Integer.MIN_VALUE;
        FindMaxPathSum(root,max);
        return max[0];
    }
    public int FindMaxPathSum(TreeNode node, int[]max){
        if(node==null){
            return 0;
        }
        
        int leftMaxSum=Math.max(0,FindMaxPathSum(node.left,max));
        int rightMaxSum=Math.max(0,FindMaxPathSum(node.right,max));  //comparing with 0 to avoid negative sum 
        
        max[0]=Math.max(max[0],leftMaxSum+rightMaxSum+node.val);
        return node.val+Math.max(rightMaxSum,leftMaxSum);
    }
--------------------------------------------------------------------------------------------------
35. Second Minimum Node in Binary Tree/BST
 public int findSecondMinimumValue(TreeNode root) {
        if(root==null){
            return -1;
        }
        
        ArrayList<Integer>list=new ArrayList<>();  
        find(root,list);
        
        if(list.size()==1){
            return -1;
        }
        
        Collections.sort(list);
        return list.get(1);
    }
    
        void find(TreeNode node,ArrayList<Integer>list){
            if(node==null){
                return;
            }
            if(!list.contains(node.val)){
                list.add(node.val);
            }
            find(node.left,list);
            find(node.right,list);
        }

------------------------------------------------------------------------------------------------
36. Minimum time to burn the binary tree
-> Intuition
-> Just apply bfs here, but before that just take a hashmap and put parents of all the nodes so that you can traverse easily in bfs.


 public static int timeToBurnTree(BinaryTreeNode<Integer> root, int start)
    {
        HashMap<BinaryTreeNode<Integer>, BinaryTreeNode<Integer>> mpp = new HashMap<>();
        BinaryTreeNode<Integer> target = bfsToMapParents(root, mpp, start);
        int maxi = findMaxDistance(mpp, target);
        return maxi;
    }

private static BinaryTreeNode<Integer> bfsToMapParents(BinaryTreeNode<Integer> root,
                                                       HashMap<BinaryTreeNode<Integer>, BinaryTreeNode<Integer>> mpp, int start) {
        Queue<BinaryTreeNode<Integer>> q = new LinkedList<>();
        q.offer(root);
        BinaryTreeNode<Integer> res = new BinaryTreeNode<>(-1);
        while(!q.isEmpty()) {
            BinaryTreeNode<Integer> node = q.poll();
            if(node.data == start) res = node;
            if(node.left != null) {
                mpp.put(node.left, node);
                q.offer(node.left);
            }
            if(node.right != null) {
                mpp.put(node.right, node);
                q.offer(node.right);
            }
        }
        return res;
    }
    private static int findMaxDistance(HashMap<BinaryTreeNode<Integer>, BinaryTreeNode<Integer>> mpp, BinaryTreeNode<Integer> target) {
        Queue<BinaryTreeNode<Integer>> q = new LinkedList<>();
        q.offer(target);
        HashMap<BinaryTreeNode<Integer>,Integer> vis = new HashMap<>();
        vis.put(target, 1);
        int maxi = 0;
        
        while(!q.isEmpty()) {
            int sz = q.size();
            int fl = 0;
            
            for(int i = 0;i<sz;i++) {
                BinaryTreeNode<Integer> node = q.poll();
                if(node.left != null && vis.get(node.left) == null) {
                    fl = 1;
                    vis.put(node.left, 1);
                    q.offer(node.left);
                }
                if(node.right != null && vis.get(node.right) == null) {
                    fl = 1;
                    vis.put(node.right, 1);
                    q.offer(node.right);
                }

                if(mpp.get(node) != null && vis.get(mpp.get(node)) == null) { //for burning parent node.
                    fl = 1;
                    vis.put(mpp.get(node), 1);
                    q.offer(mpp.get(node));
                }
            }
            if(fl == 1) maxi++;
        }
        return maxi;
    }
-----------------------------------------------------------------------------------------------
37. Root to Node Path

 private boolean getPath(TreeNode root, ArrayList<Integer> arr, int x) {
        if(root == null) {
            return false; 
        }
        arr.add(root.val);
        if(root.val == x) {
            return true; 
        }

        if(getPath(root.left, arr, x) || getPath(root.right, arr, x)) {
            return true; 
        }

        arr.remove(arr.size() - 1); 
        return false; 
    }
    public ArrayList<Integer> solve(TreeNode A, int B) {
        ArrayList<Integer> arr = new ArrayList<>(); 
        if(A == null) return arr; 
        getPath(A, arr, B); 
        return arr; 
    }
-----------------------------------------------------------------------------------------------
38. Maximum width of a binary tree
-> Width = No of nodes in a level between any two non null nodes on the same level
( first non-null node in that level <-> last non-null node in that level)

Intuition ->  we can give index to nodes by going level wise and left to right. after that we just have to take max of all the
(last idx - first idx + 1 ) in every level.
-> It may be possible that there will not be any node between two nodes of same level for that take care of index in such a way that we hypothetically considering that nodes to get the answer.
we can maintain the indexing for that cases and for the normal case by using 
for 0's based indexing->(parent = i, left child = 2*i+1, right child = 2*i+2);
But In case of Skewed tree this multiplication thing will give overflow when everytime you multiply by two.
 
-> to handle this case just do one thing whenever you get i just make it i=i-(min value idx at that level) and treat this i to find idx of children 2*i+1, 2*i+2.

class pair{
        TreeNode node;
        int idx;
        public pair(TreeNode n, int i){
            node=n;
            idx=i;
        }
    }
    public int widthOfBinaryTree(TreeNode root) {
        
        if(root==null){
            return 0;
        }
        int ans=0;
        
        Queue<pair>q=new LinkedList<>();
        q.offer(new pair(root,0)); 
        
        while(!q.isEmpty()){
            int size=q.size();
            int min=q.peek().idx; //to avoid overflow and make the idx starting from 0
            int first=0,last=0;
            for(int i=0;i<size;i++){
                int curr_idx=q.peek().idx-min;
                TreeNode rn=q.peek().node;
                q.poll();
                
                if(i==0)first=curr_idx;
                if(i==size-1)last=curr_idx;
                
                if(rn.left!=null)q.offer(new pair(rn.left,curr_idx*2+1));
                if(rn.right!=null)q.offer(new pair(rn.right,curr_idx*2+2));
                }
            ans=Math.max(ans,last-first+1);
        }
              
        return ans;
    }
-----------------------------------------------------------------------------------------------
39. Children sum property of a binary tree.
* if both children sum is less than parent, make children's value to parent's value.
* if both children values sum is greater than or equal to parent, make parent's value to children's sum.
* recursively go left and right. Traversal type: DFS.
* when coming back up the tree, take children sum and replace it in parent.
* at any point we reach null, just return (base case)
* Intuition: while going down, increase the children values to max possible so we make sure to never fall short, then all we have to do is sum both children and replace it in parent.

public static void changeTree(BinaryTreeNode < Integer > root) {
        if(root == null) return; 
        int child = 0;
        if(root.left != null) {
            child += root.left.data; 
        }
        if(root.right != null) {
            child += root.right.data; 
        }

        if(child >= root.data) root.data = child; 
        else {
            if(root.left != null) root.left.data = root.data; 
            else if(root.right != null) root.right.data = root.data; 
        }

        changeTree(root.left); 
        changeTree(root.right); 

        int tot = 0; 
        if(root.left != null) tot += root.left.data; 
        if(root.right != null) tot+= root.right.data; 
        if(root.left != null || root.right != null) root.data = tot;  
    }
-----------------------------------------------------------------------------------------------
40. Count total nodes in a complete binary tree in O(Log^2 N)

public int countNodes(TreeNode root) {
        if(root == null) return 0;
        
        int left = getHeightLeft(root);
        int right = getHeightRight(root);
        
        //If left and right are equal it means that the tree is complete and hence go for 2^h -1.
        if(left == right) return ((1<<(left)) -1);
            
        //else recursively calculate the number of nodes in left and right and add 1 for root.
        else return countNodes(root.left)+ countNodes(root.right)+1;
    }
    
    
    public int getHeightLeft(TreeNode root){
        int count=1;
        while(root.left!=null){
            count++;
            root = root.left;
        }
        return count;
    }
    
    
    public int getHeightRight(TreeNode root){
        int count=1;
        while(root.right!=null){
            count++;
            root = root.right;
        }
        return count;
    }
-----------------------------------------------------------------------------------------------
41. Serialize and Deserialize Binary Tree 
-> You can use any traversal, here i have used inorder traversal.
O(n) s(n)

 // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null)return "";
        
        Queue<TreeNode>q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        q.offer(root);
        
        while(!q.isEmpty()){
            TreeNode rn = q.poll();
            if(rn==null){
                sb.append("n "); //null
                continue;
            }
            
            sb.append(rn.val+" ");
            q.offer(rn.left);
            q.offer(rn.right);
        }
        return sb.toString();
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals(""))return null;
        
        Queue<TreeNode>q = new LinkedList<>();
        String[] values = data.split(" ");
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        q.offer(root);
        
        for(int i=1;i<values.length;i++){
            TreeNode node = q.poll();
            if(!values[i].equals("n")){ //first value for left
                TreeNode ln=new TreeNode(Integer.parseInt(values[i]));
                node.left=ln;
                q.offer(ln);
            }
            
            if(!values[++i].equals("n")){ //next value for right
                TreeNode rn=new TreeNode(Integer.parseInt(values[i])); 
                node.right=rn;
                q.offer(rn);
            }
        }

        return root;   
    }
-----------------------------------------------------------------------------------------------
42. Kth ancestor of the node
M1) Take a list and store all the ancestors of the given node and finally traverse it to find the kth ancestor.

M2) Binary Lifting <- in Extra questions section.

M3) Easy Approach
->
public int kthAncestor(Node root, int k, int node)
    {
        
        int[] K = new int[]{k};
        Node ans = KthAncestor(root,K,node);
        
    
        if(ans==null || ans.data==node)return -1;
        else return ans.data;
    }
    
    public Node KthAncestor(Node root,int[] k,int tnode){
         if(root==null)return null;
         
         if(root.data==tnode){
             return root;
         }
         
         Node left = KthAncestor(root.left,k,tnode);
         Node right = KthAncestor(root.right,k,tnode);
         
         if(left!=null && right==null){
             k[0]--;
             if(k[0]<=0){
                 //resetting k to lock the ans, since when k became 0 we got our ans.
                 // so now setting to a value so that it never reaches 0.
                 k[0] = Integer.MAX_VALUE;
                 return root;
             }
             return left;
         }
         
         if(left==null && right!=null){
             k[0]--;
             if(k[0]<=0){
                 //resetting k to lock the ans, since when k became 0 we got our ans.
                 // so now setting to a value so that it never reaches 0.
                 k[0] = Integer.MAX_VALUE;
                 return root;
             }
             return right;
         }
         return null;
    }
-----------------------------------------------------------------------------------------------
43. Print Same Distance Nodes from Target Node

M1) Map the node with their parents and store it in map, then apply bfs through the target node then for each distance just print those nodes.

M2) Without using map, just stacks and queues.
-> here were are just going left in the tree and push it in stack. and then if left is not there then right and then left if both are null then we just pop() it from the stack, we dont need to traverse the same node again so we will add two boolean leftdone and rightdone for each node.
when we get our target node we just break from the loop of stack.
->At top of the stack we have target value node.
->Now, we make use of two queues, we are just putting left node right node and from stack top the parent node.
-> We are also using set so that we can take account of the visited nodes.

O(N), S(N)
public void printSameDistanceNodesFromTarget(int tar) {

		Node root = this.root;

		Stack<pair> st = new Stack<>();
		st.push(new pair(root, false, false));

		while (!st.isEmpty()) {

			pair peek = st.peek();
			if (st.peek().node.val == tar) {
				break;
			}

			if (peek.node.left != null && !peek.ld) {
				peek.ld = true;
				st.push(new pair(peek.node.left, false, false));
			} else if (peek.node.right != null && !peek.rd) {
				peek.rd = true;
				st.push(new pair(peek.node.right, false, false));
			} else {
				int x = st.pop().node.val;
			}

		}

		// at this stage i have the all level parents of target node.

		ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
		int dis = 0;

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

		ArrayList<Integer> temp = new ArrayList<>();
		int val = st.peek().node.val;
		temp.add(val);
		ans.add(temp);

		Node goal = st.pop().node;

		q.add(goal);

		Set<Node> set = new HashSet<>();
		set.add(goal);

		while (!st.isEmpty() || !q.isEmpty() || !hq.isEmpty()) {

			Node rn = q.poll();
			
		// here we also check for { hq.isEmpty() } so that it only take once from stack for a particular distance.
		// because there might be a condition when q is not empty and we don't reach to point where update that q using hq.
		// so it may happen that at some iteration of this q we again get this below function. so had we not checked for this  					// condition it could have poped Node again from the stack (which is of another distance (currdistance+1)).
 
			if (!st.isEmpty() && !set.contains(st.peek().node) && hq.isEmpty()) {
				hq.add(st.pop().node);
			}

			if (rn.left != null && !set.contains(rn.left)) {
				hq.add(rn.left);
			}

			if (rn.right != null && !set.contains(rn.right)) {
				hq.add(rn.right);
			}

			if (q.isEmpty() && hq.isEmpty() && st.isEmpty())
				break;

			if (q.isEmpty()) {
				ArrayList<Integer> list = new ArrayList<>();

				while (!hq.isEmpty()) {
					Node item = hq.poll();
					set.add(item);
					q.offer(item);  // getting the elements from the helper queue
					list.add(item.val);
				}
				ans.add(list);
			}

		}

		int dist = 0;
		for (int i = 0; i < ans.size(); i++) {
			System.out.println("Nodes At dis = " + dis + " - > ");
			for (int j = 0; j < ans.get(i).size(); j++) {
				System.out.print(ans.get(i).get(j) + " ");
			}
			dis++;
			System.out.println();
		}

		System.out.println("-----------------");
	}
-----------------------------------------------------------------------------------------------
44. Cousins in Binary Tree (LC-993)
-> Cousins are those who are on same height of binary tree and doesn't have same parent

public boolean isCousins(TreeNode root, int x, int y) {
        Queue<TreeNode>q = new LinkedList<>();
        q.add(root);
        
        while(!q.isEmpty()){
            int len=q.size();
            boolean a_exist=false;
            boolean b_exist=false;
            
            for(int i=0;i<len;i++){
                TreeNode curr = q.poll();
                
                if(curr.val==x)a_exist = true;
                if(curr.val==y)b_exist = true;
                
                if(curr.left!=null && curr.right!=null){
                    if(( (curr.left.val==x) && (curr.right.val==y) ) 
                       ||( (curr.left.val==y) && (curr.right.val ==x) ))
                        return false;
                }
                
                if(curr.left!=null)q.add(curr.left);
                
                if(curr.right!=null)q.add(curr.right);

            }
            //here below line means both were there in the same level and also remained true hence cousins
            if(a_exist && b_exist)return true;
        }
        return false;
    }
----------------------------------------------------------------------------------------------------------------
45. Distribute Coins in Binary Tree (LC-979)

M1) 
  class Solution {
    int moves = 0;
    public int distributeCoins(TreeNode root) {
        getNumAndCoins(root);
        return moves;
    }
    
    /*
     * return [number_of_nodes_in_subtree, number_of_total_coins_in_subtree]
     */
    private int[] getNumAndCoins(TreeNode node) {
        if (node == null) return new int[] {0, 0};
        int[] left = getNumAndCoins(node.left);
        int[] right = getNumAndCoins(node.right);
        moves += Math.abs(left[0] - left[1]) + Math.abs(right[0] - right[1]);
        return new int[] {left[0] + right[0] + 1, left[1] + right[1] + node.val};
    }
}

M2) 

  public int distributeCoins(TreeNode root) {
        
 // We traverse childs first (post-order traversal), and return the balance of coins. For example, if we get '+3' from the left child, that means that the left subtree has 3 extra coins to move out. If we get '-1' from the right child, we need to move 1 coin in. So, we increase the number of moves by 4 (3 moves out left + 1 moves in right). We then return the final ballance: r->val (coins in the root) + 3 (left) + (-1) (right) - 1 (keep one coin for the root).
        
        int[] moves = new int[]{0};
        distributeCoins(root, moves);
        return moves[0];
    }
    public int distributeCoins(TreeNode node, int[]moves){
        if(node==null)return 0;
        
        int left = distributeCoins(node.left,moves);
        int right = distributeCoins(node.right,moves);
        
        moves[0] += Math.abs(left) + Math.abs(right);
        
        return node.val + left + right - 1; 
    }

----------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------