Trees

[Khandagale-Saurabh]

/**

• Definition for a binary tree node.
• public class TreeNode {
• int val;
• TreeNode left;
• TreeNode right;
• TreeNode() {}
• TreeNode(int val) { this.val = val; }
• TreeNode(int val, TreeNode left, TreeNode right) {
• this.val = val;
• this.left = left;
• this.right = right;
• }

• } */

  
  class Solution {
  ArrayList<Integer> ans=new ArrayList<Integer>();
  public int sum(TreeNode root){
        if(root==null)return 0;
  
        int left=sum(root.left);
        int right=sum(root.right);
        int ansy=left+right+root.val;
        return ansy;
  
  }
  public int rangeSumBST(TreeNode root, int low, int high)
  {
      int lsum=0,rsum=0;
  ArrayList li=new ArrayList<>();
  //   boolean status=find(root,3);

// System.out.println(status+" "+ans); int sum1=sum(root); System.out.println(sum1+" here is ans"); return 0; } public boolean find(TreeNode root,int data) { if(root==null)return false; if(root.val==data) { ans.add(root.val); return true; } boolean lft=find(root.left,data); if(lft) { ans.add(root.val); return true; }

       boolean rght=find(root.right,data);
       if(rght)
       {

ans.add(root.val); return true; }

        // System.out.println(List1);
       return false;
}

}

[Khandagale-Saurabh]

Q] Max depth

maxDept(root)
{
  if(root==null) retirn 0;

int lft=maxDept(root.left);
int rgt=maxDepth(root.right)

return Math.max(lft,right)+1;

}

Q3]Check Balance Binary Tree;

left-right<=1

[Khandagale-Saurabh]

Balance Binary Tree

Diameter of Tree : max distance between node

Green wala diamater hai Q ki uski value 10 hai aur red walw ki value 9 hai

1] left +right +2 => ye jo 2 hai vo root node k saat add krne k liye

[Khandagale-Saurabh]

Q] Node to root Path

Q] Level Order Traversal

Q] Path to Leaf from Root

Q] Remove leaf Node

[Khandagale-Saurabh]

class Solution { public int rangeSumBST(TreeNode root, int low, int high) { int ans = 0; Stack stack = new Stack(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node != null) { if (low <= node.val && node.val <= high) ans += node.val; if (low < node.val) stack.push(node.left); if (node.val < high) stack.push(node.right); } } return ans; } }

[Khandagale-Saurabh]

Q1] Sum of left leaf node

Q2] MIn Deepth in Binary Tree

public class Solution {
    /**
     * @param root: The root of binary tree
     * @return: An integer
     */
     int ans1=Integer.MAX_VALUE;
    public int minDepth(TreeNode root)
     {
          if(root==null)return 0;
          int lft=minDepth(root.left);
          int rgt=minDepth(root.right);
           if(lft==0)
           {
               return rgt+1;
           }  
             if(rgt==0)
           {
               return lft+1;
           }  
          int ans=Math.min(lft,rgt)+1;

        //   System.out.print(ans1);
          return ans;
      }
}

Q 3] Example 2:

Input: root = {8,3,10,1,6,#,14,#,#,4,7,13,#} 8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13 Output: {1,#,3,#,4,#,6,#,7,#,8,#,10,#,13,#,14} Explanation: 1 \ 3 \ 4 \ 6 \ 7 \ 8 \ 10 \ 13 \ 14

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    TreeNode ans=new TreeNode(0);
    TreeNode curr=ans;
    public TreeNode increasingBST(TreeNode root)
   {
      TreeNode aa= increasingBST1(root);
      return ans.right;
   }
    public TreeNode increasingBST1(TreeNode root)
    {
        if(root==null)return null;
       TreeNode lft=increasingBST(root.left);
       TreeNode nd=root;
       root.left=null;
       curr.right=nd;
       curr=root; 
       TreeNode rgt=increasingBST(root.right);
       return ans;
    }
}

[Khandagale-Saurabh]

Q] Lonly Node in bst

[Khandagale-Saurabh]

Lowest Comon Ansterster

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    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 lef=lowestCommonAncestor(root.left,p,q);
        TreeNode righ=lowestCommonAncestor(root.right,p,q);

        if(lef==null)
        {
            return righ;
        }

        if(righ==null)
        {
            return lef;
        }

        return root; // left != null && right!=null
    }
}

or

 if(root == null || root == p || root == q)return root;

        TreeNode left = lowestCommonAncestor(root.left, p , q);
        TreeNode right = lowestCommonAncestor(root.right, p ,q);

        if(left == null)return right;
        if(right == null)return left;
        else{
            return root;
        }