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
-----------------------------------------------------------------------------------
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;
	}
-----------------------------------------------------------------------------------	
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;
    }
-----------------------------------------------------------------------------------	
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(rn.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.
-----------------------------------------------------------------------------------	
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;
    }
-----------------------------------------------------------------------------------	
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
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;
		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;
	}
-----------------------------------------------------------------------------------	
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.
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);
}
			
-----------------------------------------------------------------------------------
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); 
} 
-----------------------------------------------------------------------------------
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;
    }
-----------------------------------------------------------------------------------
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
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;
    }
--------------------------------------------------------------------------------------------------
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);
        }