BinaryTree

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.LinkedList;

public class BinaryTree {

    public static class Node {
        int data;
        Node left;
        Node right;

        Node(int data, Node left, Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }


    public static class Pair {
        Node node;
        int state;

        Pair(Node node, int state) {
            this.node = node;
            this.state = state;
        }
    }


    public static Node construct(Integer[] arr)
    {
        Node root = new Node(arr[0], null, null);
        Pair rtp = new Pair(root, 1);

        Stack<Pair> st = new Stack<>();
        st.push(rtp);

        int idx = 0;
        while (st.size() > 0) {
            Pair top = st.peek();
            if (top.state == 1) {
                idx++;
                if (arr[idx] != null) {
                    top.node.left = new Node(arr[idx], null, null);
                    Pair lp = new Pair(top.node.left, 1);
                    st.push(lp);
                } else {
                    top.node.left = null;
                }

                top.state++;
            } else if (top.state == 2) {
                idx++;
                if (arr[idx] != null) {
                    top.node.right = new Node(arr[idx], null, null);
                    Pair rp = new Pair(top.node.right, 1);
                    st.push(rp);
                } else {
                    top.node.right = null;
                }

                top.state++;
            } else {
                st.pop();
            }
        }

        return root;
    }

    public static void display(Node node) {
        if (node == null) {
            return;
        }

        String str = "";
        str += node.left == null ? "." : node.left.data + "";
        str += " <- " + node.data + " -> ";
        str += node.right == null ? "." : node.right.data + "";
        System.out.println(str);

        display(node.left);
        display(node.right);
    }

    public static int size(Node node) {
        // write your code here

        if(node==null)
        {
            return 0;
        }
        int ls=size(node.left);
        int rs=size(node.right);
        int cs=ls+rs+1;
        return cs;
    }

    public static int sum(Node node) {
        // write your code here
        if(node==null)
        {
            return 0;
        }
        int ls=sum(node.left);
        int rs=sum(node.right);
        int cs=ls+rs+node.data;
        return cs;
    }

    public static int max(Node node) {
        // write your code here
        if(node==null)
        {
            return Integer.MIN_VALUE;
        }
        int lm=max(node.left);
        int rm=max(node.right);
        int cm= Math.max(Math.max(lm,rm), node.data);
        return cm;

    }

    //https://leetcode.com/problems/add-one-row-to-tree/?envType=problem-list-v2&envId=binary-tree
    public Node addOneRow(Node root, int v, int d) {
        if (d == 1) return new Node(v, root, null);
        else if (d == 2) {
            root.left = new Node(v, root.left, null);
            root.right = new Node(v, null, root.right);
        } else {
            if (root.left != null) addOneRow(root.left, v, d-1);
            if (root.right != null) addOneRow(root.right, v, d-1);
        }
        return root;
    }

    public static int height(Node node) {
        // write your code here
        if(node==null)
        {
            return -1;
        }

        int lh=height(node.left);
        int rh=height(node.right);
        int h=Math.max(lh,rh)+1;

        return h;
    }

    static void travelsal(Node node)
    {
        if(node==null)
        {
            return;
        }
        System.out.println("pre "+node.data);
        travelsal(node.left);
        System.out.println("in "+node.data);
        travelsal(node.right);
        System.out.println("post "+node.data);
    }


    public static void levelOrder(Node node) {
        // write your code here
        Queue<Node> queue=new ArrayDeque<>();
        queue.add(node);
        while(queue.size()>0)
        {
            int size=queue.size();
            for(int i=0;i<size;i++) {
                node = queue.remove();
                System.out.print(node.data + " ");
                if (node.left != null) {
                    queue.add(node.left);
                }

                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            System.out.println();
        }
    }

    //https://leetcode.com/problems/house-robber-iii/
    public int rob(Node root) {
        if(root == null){
            return 0;
        }
        rob(root.left);
        rob(root.right);

        int a = root.data;
        int b = 0;

        if(root.left != null){
            // left child
            b += root.left.data;

            // both left grandchildren
            if(root.left.left != null){
                a += root.left.left.data;
            }
            if(root.left.right != null){
                a += root.left.right.data;
            }
        }

        if(root.right != null){
            // right child
            b += root.right.data;

            // both right grandchildren
            if(root.right.left != null){
                a += root.right.left.data;
            }
            if(root.right.right != null){
                a += root.right.right.data;
            }
        }

        System.out.println("a "+a);
        System.out.println("b "+b);
        root.data = Math.max(a, b);
        return root.data;
    }

    public int rob1(Node node) {
       List<Node> list = new LinkedList<>();
       list.add(node);
       int sum1 = 0;
       int sum2 = 0;
       int level = 1;
       while(list.size()>0) {
           int size = list.size();
           for(int i = 0;i<size;i++) {
               if(level%2!=0) {
                   sum1+= list.get(i).data;
               } else {
                   sum2+= list.get(i).data;
               }

           }
           level++;
           for(int i = 0;i<size;i++) {
               node = list.removeFirst();

               if (node.left != null) {
                   list.add(node.left);
               }
               if (node.right != null) {
                   list.add(node.right);
               }
           }

       }
        return Math.max(sum1,sum2);
    }

    static void levelOrderLinewise(Node node)
    {
        Queue<Node> queue=new ArrayDeque<>();
        queue.add(node);
        while(queue.size()>0)
        {
            node = queue.remove();
            System.out.print(node.data + " ");
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        System.out.println();
    }

    public static void iterativePrePostInTraversal(Node node) {
        // write your code here
        Stack<Pair> stack=new Stack<>();
        Pair rp=new Pair(node,1);
        stack.push(rp);
        String pre="";
        String in="";
        String post="";
        while(stack.size()>0)
        {
            Pair top=stack.peek();
            if(top.state==1)//pre,s++,left
            {
                pre+=top.node.data+" ";
                top.state++;

                if(top.node.left!=null)
                {
                    Pair lp=new Pair(top.node.left,1);
                    stack.push(lp);
                }

            }
            else if(top.state==2)
            {
                in+=top.node.data+" ";
                top.state++;

                if(top.node.right!=null)
                {
                    Pair lp=new Pair(top.node.right,1);
                    stack.push(lp);
                }

            }
            else {
                post+=top.node.data+" ";
                stack.pop();

            }
        }

        System.out.println(pre);
        System.out.println(in);
        System.out.println(post);
    }


    public static boolean find(Node node, int data, ArrayList<Node> list){
        // write your code here
        if(node==null)
        {
            return false;
        }
        if(data==node.data)
        {
            list.add(node);
            return true;
        }

        boolean lc=find(node.left,data,list);
        if(lc)
        {
            list.add(node);
            return true;
        }

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

        return false;
    }


void kLevelDown(Node node,int k,int blocker)
{
    if(node == null && k<0 || node.data == blocker)
    {
        return;
    }
    if(k == 0)
    {
        System.out.println(node.data);
    }
    kLevelDown(node.left,k-1,blocker);
    kLevelDown(node.right,k-1,blocker);
}

    ArrayList<Node> path=new ArrayList<>();
    void printkNodeFar(Node node,int data,int k)
    {
        path = new ArrayList<>();
        find(node,data,path);
        for(int i = 0; i<path.size();i++)
        {
            kLevelDown(path.get(i),k-i ,i == 0?null:path.get(i-1).data);
        }
    }

    static List<Integer> distanceK(Node root, int target, int k) {
        List<Node> list = new ArrayList<>();
        List<Integer> result = new ArrayList<>();

        find1(root,target,list);
        for(int i = 0;i<list.size();i++)
        {
            kLevelDown(list.get(i),k-i,i == 0?null:list.get(i-1),result);
        }
        //  System.out.print(list);
        return result;
    }

    public static void kLevelDown(Node node,int k,Node blocker,List<Integer> list)
    {
        if(node == null || k<0 ||node == blocker)
        {
            return;
        }
        if(k == 0)
        {
            System.out.println(node.data);
            list.add(node.data);
        }
        kLevelDown(node.left,k-1,blocker,list);
        kLevelDown(node.right,k-1,blocker,list);

    }

    public static boolean find1(Node node,int data,List<Node> list)
    {
        if(node == null)
        {
            return false;
        }
        if(node.data == data)
        {
            list.add(node);
            return true;
        }
        boolean lc = find1(node.left,data,list);
        if(lc)
        {
            list.add(node);
            return true;
        }
        boolean rc = find1(node.left,data,list);
        if(rc)
        {
            list.add(node);
            return true;
        }
        return false;
    }


    static void pathToLeavefromRoot(Node node ,String path , int sum,int low,int high)
    {
        if(node == null)
        {
            return;
        }
        if(node.left!= null && node.right!= null)
        {
            sum+=node.data;
            if(sum<=low && sum>=high)
            {
                System.out.println(path+node.data);
            }
        }
        pathToLeavefromRoot(node.left,path+node.data+" ",sum +node.data,low,high);
        pathToLeavefromRoot(node.right,path+node.data+" ",sum +node.data,low,high);
    }

    static Node createLeftCloneTree(Node node)
    {
        if(node == null)
        {
            return null;
        }
      Node lcr = createLeftCloneTree(node.left);
     Node rcr = createLeftCloneTree(node.right);
     Node nn = new Node(node.data,lcr,null);
     node.left = nn;
     node.right = rcr;
     return node;
    }

    static Node transformBackFromLeftCloneTree(Node node)
    {
        if(node == null)
        {
            return null;
        }
        Node lcr = transformBackFromLeftCloneTree(node.left.left);
        Node rcr = transformBackFromLeftCloneTree(node.right);
        node.left = lcr;
        node.right = rcr;
        return node;
    }

    public static int diameter(Node node)
    {
        if(node == null)
        {
            return 0;
        }
        //max distance between 2 nodes in LHS
        int ld = diameter(node.left);
        //max distance between 2 nodes in RHS
        int rd = diameter(node.right);
        //max distance between left deepest node and right deepest node
        int f = height(node.left)+height(node.right)+2;
        int dia = Math.max(f,Math.max(ld,rd));
        return dia;
    }

    static class DiaPair{
        int ht;
        int dia;
    }

    public static DiaPair diameter1(Node node)
    {
        if(node == null)
        {
            DiaPair bp = new DiaPair();
            bp.ht = -1;
            bp.dia = 0;
        }
        DiaPair lp = diameter1(node.left);
        DiaPair rp = diameter1(node.right);
        DiaPair mp = new DiaPair();
        mp.ht = Math.max(lp.ht,rp.ht)+1;
        int fes = lp.ht + rp.ht +2;
        mp.dia = Math.max(fes,Math.max(lp.dia,rp.dia));
        return mp;
    }

    static void printSingleChildNode(Node node,Node parent)
    {
        if(node == null)
        {
            return;
        }
        if(parent!=null && parent.left == node && parent.right ==null)
        {
            System.out.println(node.data);
        }
        if(parent!=null && parent.right == node && parent.left ==null)
        {
            System.out.println(node.data);
        }
        printSingleChildNode(node.right,node);
        printSingleChildNode(node.left,node);
    }

    static Node removeLeaves(Node node) {
        if(node == null)
        {
            return null;
        }
        if(node.left == null && node.right == null)
        {
            return null;
        }
        node.left =  removeLeaves(node.left);
       node.right = removeLeaves(node.right);
       return node;
    }
    static int tilt = 0;
    public static int tilt(Node node)
    {
        if(node == null)
        {
            return 0;
        }
        int leftTilt = tilt(node.left);
        int rightTilt = tilt(node.right);
        int localTilt = Math.abs(leftTilt-rightTilt);
        tilt+=localTilt;
        int totalSum = leftTilt + rightTilt +node.data;
        return totalSum;
    }
    static class BSTPair
    {
        boolean isBst;
        int min;
        int max;
    }
    static class BST
    {
        boolean isBst;
        int min;
        int max;
        Node root;
        int size;
    }
    static BST isLargestBST(Node node)
    {
        if(node == null)
        {
            BST bst = new BST();
            bst.isBst = true;
            bst.min = Integer.MAX_VALUE;
            bst.max = Integer.MIN_VALUE;
            bst.root = null;
            bst.size = 0;
        }
        BST lbp = isLargestBST(node.left);
        BST rbp = isLargestBST(node.left);
        BST mp = new BST();
        mp.isBst = lbp.isBst && rbp.isBst && (node.data>=lbp.max && node.data<=rbp.min);
        mp.min = Math.min(node.data,Math.min(lbp.min,rbp.min));
        mp.max = Math.max(node.data,Math.max(lbp.max,rbp.max));
        if(mp.isBst)
        {
            mp.root = node;
            mp.size = lbp.size + rbp.size + 1;
        }
        else if(lbp.size>rbp.size)
        {
            mp.root = lbp.root;
            mp.size = lbp.size;
        }
        else {
            mp.root = rbp.root;
            mp.size = rbp.size;
        }
        return mp;
    }

    public static BSTPair isBST(Node node)
    {
        if(node == null)
        {
            BSTPair bstPair = new BSTPair();
            bstPair.min = Integer.MAX_VALUE;
            bstPair.max = Integer.MIN_VALUE;
        }
        BSTPair lbp = isBST(node.left);
        BSTPair rbp = isBST(node.right);
        BSTPair mp = new BSTPair();
        mp.isBst = lbp.isBst && rbp.isBst && (node.data>=lbp.max && node.data<=rbp.min);
        mp.min = Math.min(node.data,Math.min(lbp.min,rbp.min));
        mp.max = Math.max(node.data,Math.max(lbp.max,rbp.max));
      return mp;
    }
//https://leetcode.com/problems/validate-binary-search-tree/
    public boolean isValidBST(Node root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean isValidBST(Node root, long minVal, long maxVal) {
        if (root == null) {
            return true;
        }
        if (root.data >= maxVal || root.data <= minVal) {
            return false;
        }
        boolean lc = isValidBST(root.left, minVal, root.data);
        boolean rc = isValidBST(root.right, root.data, maxVal);
        boolean res = lc && rc;
        return res;
    }

    public static boolean isBalanced(Node node)
    {
        if(node == null)
        {
            return true;
        }
        boolean lp = isBalanced(node.left);
        boolean rp = isBalanced(node.right);
        int a = Math.abs(height(node.left)-height(node.right));
        if(a>1 || lp || rp)
        {
            return false;
        }
        return true;
    }
static boolean isBalance =true;
    public static int largestBst(Node node)
    {
        if(node == null)
        {
            return 0;
        }
        int lp = largestBst(node.left);
        int rp = largestBst(node.right);
        int gap = Math.abs(height(node.left)-height(node.right));
       if(gap>1)
       {
           isBalance = false;
       }
       int th = Math.max(lp,rp)+1;
       return th;
    }
//https://leetcode.com/problems/binary-tree-paths/description/
    public List<String> binaryTreePaths(Node root) {

        List<String> list = new ArrayList<>();
        solve(root,"",list);
        return list;
    }
    void solve(Node root , String str,List<String> list) {
        if(root == null) {
            return;
        }
        if(root.left == null && root.right == null)
        {
            str = str+String.valueOf(root.data);
            list.add(str);
            return;
        }
        else {
            str = str+String.valueOf(root.data)+"->";
        }
        solve(root.left,str,list);
        solve(root.right,str,list);
    }
//https://leetcode.com/problems/path-sum/description/
    public boolean hasPathSum(Node node, int targetSum) {
        if(node == null) {
            return false;
        }
        if(node.left == null && node.right == null) {
            return targetSum == node.data;
        }
        targetSum = targetSum-node.data;

        boolean leftSum = hasPathSum(node.left, targetSum);
        boolean rightSum = hasPathSum(node.right, targetSum);
        return leftSum||rightSum;
    }
//https://leetcode.com/problems/sum-root-to-leaf-numbers/description/
    static int sumNumbers(Node root) {
        recursion(root, 0);
        return ans;
    }
    static int ans = 0;
    static void recursion(Node root, int sum){
        if(root==null){
            return;
        }
        if(root.left == null && root.right == null){
            ans += ((sum*10) + root.data);
            return;
        }
        recursion(root.left, sum * 10 + root.data);
        recursion(root.right, sum * 10 + root.data);
    }
// https://leetcode.com/problems/sum-of-left-leaves/
    public int sumOfLeftLeaves(Node root) {
        return helpher(root);
    }
    public static int helpher(Node root){
        if(root==null) {
            return 0;
        }
        int ans=0;
        if(root.left != null && root.left.left == null && root.left.right == null)
        {
            ans+=root.left.data;
        }
        ans+=helpher(root.left);
        ans+=helpher(root.right);
        return ans;
    }

    int min = Integer.MAX_VALUE;
    public int getMinimumDifference(Node node) {
        if(node == null) {
            return Integer.MAX_VALUE;
        }

        if(node.left!= null && node.right!= null) {
            int res1 = Math.abs(node.left.data - node.data);
            int res2 = Math.abs(node.right.data - node.data);
            int res3 = Math.abs(node.left.data - node.right.data);
            min = Math.min(res1,Math.min(res2,res3));
        }
        if(node.left == null && node.right!= null) {
            min = Math.abs(node.right.data-node.data);
        }
        if(node.left!= null && node.right == null) {
            min = Math.abs(node.left.data-node.data);
        }
        int lc = getMinimumDifference(node.left);
        int rc = getMinimumDifference(node.right);
        return min;
    }
    List<Integer> modes = new ArrayList<>();
    public int[] findMode(Node root) {
        inorder(root);
        int[] ans = new int[modes.size()];
        for (int i = 0; i < modes.size(); i++) {
            ans[i] = modes.get(i);
        }
        return ans;
    }
   Integer current = Integer.MIN_VALUE;
    int count = 0;
    int max = Integer.MIN_VALUE;

    private void inorder(Node node) {
        if (node == null) {
            return;
        }
        inorder(node.left);
        // Handle the current node
             if(node.data == current) {  // If the value is the same as the previous one
                 count++;  // Increment count for the current value
             } else {  // If the current value is different from the previous one
                 current = node.data; // Update current value
                 count = 1; // Reset count for the new value
             }
        // Update the list of modes based on the current count
         if(count>max) {  // If current count exceeds max found so far
             max = count;
             modes.clear(); // Clear previous modes
             modes.add(node.data);  // Add the new mode
         } else if(count == max) { // If the current count equals the max count
             modes.add(node.data);  // Add the current value to the list of modes
         }
        inorder(node.right);

    }

    Node prev = null;
    public boolean isUnivalTree(Node node) {
        if(node == null) {
            return false;
        }
        isUnivalTree(node.left);
        if(prev!= null) {
            if(prev.data!= node.data) {
                return false;
            }
        }
        isUnivalTree(node.right);
        return true;
    }

    //https://leetcode.com/problems/cousins-in-binary-tree/
    int xDepth = -1, yDepth = -1;
    Node xParent = null, yParent = null;
    public boolean isCousins(Node root, int x, int y) {

        findisCousins(root, null, x, y, 0);
        return(xDepth == yDepth) && (xParent != yParent);

    }

    public void findisCousins(Node node, Node parent, int x, int y, int depth)
    {
        if(node == null)
            return;

        if(node.data == x)
        {
            xDepth = depth;
            xParent = parent;
        }
        else if(node.data == y)
        {
            yDepth = depth;
            yParent = parent;
        }

        if(xParent == null || yParent == null)
        {
            findisCousins(node.left, node, x, y, depth+1);
            findisCousins(node.right, node, x, y, depth+1);
        }
    }
//https://leetcode.com/problems/binary-tree-right-side-view/
    public List<Integer> rightSideView(Node root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    }
    public void rightView(Node curr, List<Integer> result, int currDepth){
        if(curr == null){
            return;
        }
        if(currDepth == result.size()){

            result.add(curr.data);
        }
        rightView(curr.right, result, currDepth + 1);
        rightView(curr.left, result, currDepth + 1);

    }
//https://leetcode.com/problems/all-possible-full-binary-trees/
    List<List<Node>> dp = new ArrayList<>();
    public List<Node> allPossibleFBT(int n) {
        for (int i = 0; i <= n; i++) {
            dp.add(new ArrayList<>());
        }
        System.out.println(dp);
        return solveallPossibleFBT(n);
    }


    List<Node> solveallPossibleFBT(int n) {

        if(n%2 == 0) {
            return new ArrayList<>();
        }
        if (!dp.get(n).isEmpty())
            return dp.get(n);
        if(n == 1) {
            Node node = new Node(0,null,null);
            List<Node> res = new ArrayList<>();
            res.add(node);
            return res;
        }

        List<Node> res = new ArrayList<>();

        for(int i = 1;i<n;i +=2) {
            List<Node> lc = solveallPossibleFBT(i);
            List<Node> rc = solveallPossibleFBT(n-i-1);



            for(Node l :lc) {
                for(Node r : rc) {
                    System.out.println("rc "+l.data);
                    System.out.println("lc "+r.data);
                    Node node = new Node(0,l,r);

                    System.out.println("res "+res);
                    res.add(node);
                }
            }

        }

        dp.set(n, res);
        return res;

    }

    public Node lowestCommonAncestor(Node node, int p, int q) {
        if(node == null ||node.data == p ||node.data == q)
        {
            return node;
        }

        Node left = lowestCommonAncestor(node.left,p,q);
        Node right = lowestCommonAncestor(node.right,p,q);

        if(left != null && right != null)
            return node;
        return left != null ? left : right;

    }
//https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/solutions/78551/7-lines-easy-java-solution/
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        int diff = 1;
        for (String node: nodes) {
            if (--diff < 0) return false;
            if (!node.equals("#")) diff += 2;
        }
        return diff == 0;
    }
    public int findBottomLeftValue1(Node root) {
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        Node leftmost = null;
        while (!q.isEmpty()) {
            leftmost = q.poll();
            if (leftmost.right != null) {
                q.offer(leftmost.right);
            }
            if (leftmost.left != null) {
                q.offer(leftmost.left);
            }
        }

        return leftmost.data;
    }

    int height;
    int level;
    public int findBottomLeftValue(Node node) {
        height = -1;
        ans = -1;
        findBottomLeftValueSolve(node,0);
        return ans;
    }

    void findBottomLeftValueSolve(Node root,int level) {
        if(root == null) return;
        if(level > height) {
            height = level;
            ans = root.data;
        }
        findBottomLeftValueSolve(root.left,level+1);
        findBottomLeftValueSolve(root.right,level+1);
    }

    public static void main(String[] args) throws IOException {

      /*  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Integer[] arr = new Integer[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            if (!values[i].equals("n") ) {
                arr[i] = Integer.parseInt(values[i]);
            } else {
                arr[i] = null;
            }
        }*/

        Integer[] arr = {50,25,12,null,null,37,30,null,null,null,75,62,null,72,null,null,87,null,null};
        //Integer[] arr = {5,4,11,7,null,null,2,null,null,null,8,13,4,null,null,4,null,1,null,null,null};
       // Integer[] arr = {100,null,100,200,null,null,null};
       // Integer[] arr = {1,2,4,5,null,null,null,null,3,null,null};
        Node root = construct(arr);
       // tilt(root);
      //  isBalanced1(root);
     //   System.out.println(isBalance);
    //    BST bst = isLargestBST(root);
     //   System.out.println(bst.root+"@"+bst.size);
       // levelOrder(root);
    //  Node nnn =  removeLeaves(root);
     //   levelOrder(nnn);
     //   BinaryTree binaryTree = new BinaryTree();
      //  DiaPair diaPair = new DiaPair();
      //  diameter1(root);
      //  System.out.println(diaPair.dia);
       // binaryTree.kLevelDown(root,1);
        //  display(root);
        //  System.out.println(size(root));
         // System.out.println(max(root));
        //  System.out.println(height(root));
        //
        // travelsal(root);
        //  levelOrder(root);
        //  iterativePrePostInTraversal(root);
      //  ArrayList<Node> list=new ArrayList<>();
       // find(root,30,list);
      //  System.out.println(list);
      //  distanceK(root,25,2);
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.rob1(root);
      //  binaryTree.isValidBST(root);
       // boolean res = binaryTree.hasPathSum(root,22);
      // List<Integer> res = binaryTree.lowestCommonAncestor(root,25,72);
       // System.out.println(res);
        String ss = "9,3,4,#,#,1,#,#,2,#,6,#,#";
        binaryTree.isValidSerialization(ss);
        binaryTree.addOneRow(root,1,3);

        binaryTree.allPossibleFBT(7);
    }

}