import java.util.*;
import java.util.LinkedList;

public class Trees {
    public static class node{
        int data;
        node left,right;

        public node(int data){
            this.data=data;
            this.left=null;
            this.right=null;
        }
    }
    public static int height(node root){
        if(root==null) return 0;
        int lh=height(root.left);
        int rh=height(root.right);
        return Math.max(lh,rh)+1;
    }

    public static int count(node root){
        if(root==null) return 0;
        return count(root.right) + count(root.left) +1;
    }

    public static int sum(node root){
        if(root == null) return 0;
        return sum(root.left)+sum(root.right) + root.data;
    }

    public static int diameter(node root){
        if(root==null) return 0;
        int lh=height(root.left);
        int rh=height(root.right);
        int ld=diameter(root.left);
        int rd=diameter(root.right);
        int selfD=lh+rh+1;
        return Math.max(selfD,Math.max(ld,rd));
    }

    static class info{
        int diam;
        int ht;

        info(int diam,int ht){
            this.diam=diam;
            this.ht=ht;
        }
    }
    public static info Diameter(node root){
        if(root ==null) return new info(0,0);
        info leftInfo=Diameter(root.left);
        info rightInfo=Diameter(root.right);
        int ht=Math.max(leftInfo.ht, rightInfo.ht)+1;
        int diam=Math.max(Math.max(leftInfo.diam,rightInfo.diam), leftInfo.ht+rightInfo.ht+1);
        return new info(diam,ht);
    }

    public static boolean isSubtree(node root, node subRoot){
        if(root==null) return false;
        if(root.data==subRoot.data){
            if(isIdentical(root,subRoot))
                return true;
        }
        return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }

    public static boolean isIdentical(node root, node subRoot){
        if(root==null && subRoot==null) return true;
        else if (root==null||subRoot==null || root.data!=subRoot.data) return false;
        if(!isIdentical(root.left,subRoot.left)) return false;
        if(!isIdentical(root.right,subRoot.right)) return false;
        return true;
    }

    static class information{
        node node;
        int hd;
        public information(node node,int hd){
            this.node=node;
            this.hd=hd;
        }
    }
    public static void topView(node root){
        Queue<information> q=new LinkedList<>();
        HashMap<Integer,node> map = new HashMap<>();

        int min=0,max=0;
        q.add(new information(root,0));
        q.add(null);
        while(!q.isEmpty()){
            information curr=q.remove();
            if (curr == null) {
                if (q.isEmpty()) break;
                else q.add(null);
            }
            else{
                if(!map.containsKey(curr.hd)) map.put(curr.hd, curr.node);
                if(curr.node.left!=null) {
                    q.add(new information(curr.node.left, curr.hd - 1));
                    min = Math.min(min, curr.hd - 1);
                }
                if(curr.node.right!=null) {
                    q.add(new information(curr.node.right, curr.hd + 1));
                    max = Math.max(curr.hd + 1, max);
                }
            }
        }
        for(int i=min;i<=max;i++){
            System.out.print(map.get(i).data + " ");
        }
    }

    public static ArrayList<ArrayList<Integer>> levelOrder(node root){
    Queue<node> q=new LinkedList<>();
    ArrayList<Integer> arr=new ArrayList<>();
    ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
    q.add(root);
    q.add(null);
    while(!q.isEmpty()){
        while(q.peek()!=null) {
            if (q.peek().left != null) q.add(q.peek().left);
            if (q.peek().right != null) q.add(q.peek().right);
            arr.add(q.peek().data);
            q.remove();
        }
            q.add(null);
            q.remove();
            ans.add(arr);
            arr=new ArrayList<>();
            if(q.size()==1 && q.peek()==null) break;
    }
    Collections.reverse(ans);
    return  ans;
    }

    public static void kLevel(node root, int level, int k){
        if(level==k){
            System.out.print(root.data + " ");
            return;
        }
        else{
            kLevel(root.left,level+1,k);
            kLevel(root.right,level+1,k);
        }
    }

    public static int lowestCommonAncestor(node root, int n1, int n2){
        // Store the paths of both nodes in arraylist and iterate
        ArrayList<node> path1=new ArrayList<>();
        ArrayList<node> path2=new ArrayList<>();
        getPath(root,n1,path1);
        getPath(root,n2,path2);
        int i=0;
        for(;i< path1.size()&&i< path2.size();i++){
            if(path1.get(i) != path2.get(i)) break;
        }
        return path1.get(i-1).data;
    }
    public static boolean getPath(node root, int n, ArrayList<node> path){
        if(root==null) return false;
        path.add(root);
        if(root.data==n) return true;
        boolean foundLeft=getPath(root.left,n,path);
        boolean foundRight=getPath(root.right,n,path);
        if(foundLeft||foundRight) return true;
        path.remove(path.size()-1);
        return false;
    }

    public static node lca(node root, int n1, int n2){
        //both the nodes belong to the same subtree of lca root.
        if( root==null || root.data==n1 || root.data==n2) return root;
        node leftLca=lca(root.left,n1,n2);
        node rightLca=lca(root.right,n1,n2);
        if(leftLca==null) return rightLca;
        if(rightLca==null) return leftLca;
        return root;
    }



    public static int minDistance(node root, int n1, int n2){
        node lca= lca(root,n1,n2);//calculate the separate distances from both the nodes to the lca.
        return distance(lca,n1) + distance(lca,n2);
    }
    public static int distance(node root, int n){
        //calculating the distance from root(lca) to the given node n.
        if(root==null) return -1;
        if(root.data==n) return 0;
        int leftDistance=distance(root.left,n);
        int rightDistance=distance(root.right,n);
        if(leftDistance==-1) return rightDistance+1;
        else return leftDistance+1;
    }

    public static int kthAncestor(node root, int n, int k){
        if(root==null) return -1;
        if(root.data==n) return 0;
        int leftDist=kthAncestor(root.left,n,k);
        int rightDist=kthAncestor(root.right,n,k);
        if(leftDist==-1 && rightDist==-1) return -1;
        int max=Math.max(leftDist,rightDist);
        if(max+1==k) System.out.println(root.data);
        return max+1;
    }


    public static int  sumTree(node root){
        if(root==null) return 0;
        int leftChild=sumTree(root.left);
        int rightChild=sumTree(root.right);
        int data=root.data;
        int newLeft=root.left==null?0:root.left.data;
        int newRight=root.right==null?0:root.right.data;
        root.data=leftChild + rightChild + newLeft+newRight;
        return data;
    }

    public static void preOrder(node root){
        if(root==null) return;
        System.out.print(root.data + " ");
        preOrder(root.left);
        preOrder(root.right);

    }

    public node removeLeafNodes(node root, int target) {
        if(root==null) return null;
        root.left=removeLeafNodes(root.left,target);
        root.right=removeLeafNodes(root.right,target);
        if(root.left==null && root.right==null){
            if(root.data==target) return null;
        }
        return root;
    }

    public node invertTree(node root) {
        if(root==null) return null;
        else if (root.left==null && root.right==null) return root;
        node m=invertTree(root.left);
        node n=invertTree(root.right);
        root.left=n;
        root.right=m;
        return root;
    }
    public static void main(String[] args){
        node root =new node(1);
        root.left=new node(2);
        root.right=new node(3);
        root.left.left=new node(4);
        root.left.right=new node(5);
        root.right.left=new node(6);
        root.right.right=new node(7);
        sumTree(root);
        preOrder(root);
    }
}