import java.util.*;

public class Solution {

    public static Boolean isLeaf(TreeNode root) {

        return (root.left == null) && (root.right == null);

    }

    public static void addLeftBoundary(TreeNode root, ArrayList<Integer>res)

    {

        TreeNode cur = root.left;

        while (cur != null) {

            if (isLeaf(cur) == false) res.add(cur.data);

            if (cur.left != null) cur = cur.left;

            else cur = cur.right;

        }

    }

    public static void addRightBoundary(TreeNode root, ArrayList<Integer>res)

    {

        TreeNode cur = root.right;

        ArrayList < Integer > tmp = new ArrayList < Integer > ();

        while (cur != null) {

            if (isLeaf(cur) == false) tmp.add(cur.data);

            if (cur.right != null) cur = cur.right;

            else cur = cur.left;

        }

        int i;

        for (i = tmp.size() - 1; i >= 0; --i) {

            res.add(tmp.get(i));

        }

    }

    public static void addLeaves(TreeNode root, ArrayList < Integer > res) {

        if (isLeaf(root)) {

            res.add(root.data);

            return;

        }

        if (root.left != null) addLeaves(root.left, res);

        if (root.right != null) addLeaves(root.right, res);

    }

    public static List<Integer> traverseBoundary(TreeNode root){

        // Write your code here.

        ArrayList<Integer>ans=new ArrayList<>();

        if(isLeaf(root)==false) ans.add(root.data);

        addLeftBoundary(root, ans);

        addLeaves(root, ans);

        addRightBoundary(root, ans);

        return ans;

    }

}

public class Solution

{

    public static int minValue(Node root) {

        // Write your code here.

        if(root==null)

        {

            return -1;

        }

        if(root.left!=null)

        {

            return minValue(root.left);

        }

        else return root.data;

    }

}

import java.util.* ;

import java.io.*; 

public class Solution {

    public static  void rec(int indx,ArrayList<ArrayList<Integer>> ans,ArrayList<Integer> arr)

    {

        if(indx==arr.size())

        {

            ArrayList<Integer> temp=new ArrayList<>();

            for(int i:arr)

            {

                temp.add(i);

            }

            ans.add(new ArrayList<>(temp));

        }

        else

        {

            for(int i=indx;i<arr.size();i++)

            {

                swap(i,indx,arr);

                rec(indx+1, ans, arr);

                swap(i,indx,arr);//backtracking

            }

        }

    }

    public static void swap(int a,int b,ArrayList<Integer> arr)

    {

        Collections.swap(arr, a, b);

    }

    static ArrayList<ArrayList<Integer>> permutations(ArrayList<Integer> arr, int size) {

        // Write your code here.

        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();

        rec(0,ans,arr);

        return ans;

    }

}

class Pair

{

    int hd;

    BinaryTreeNode node;

    public Pair(int hd,BinaryTreeNode node)

    {

        this.hd=hd;

        this.node=node;

    }

}public class Solution {

    public static ArrayList<Integer> getTopView(BinaryTreeNode root) {

        // Write your code here.

         ArrayList<Integer> list=new ArrayList<>();

        if(root==null) return list;

        Map<Integer,Integer> map=new TreeMap<>();

        Queue<Pair> q=new LinkedList<>();

        q.add(new Pair(0,root));

        while(!q.isEmpty())

        {

            Pair curr=q.poll();

            if(!map.containsKey(curr.hd))

            {

                map.put(curr.hd,curr.node.val);

            }

            if(curr.node.left!=null)

            {

                q.add(new Pair(curr.hd-1,curr.node.left));

            }

            if(curr.node.right!=null)

            {

                q.add(new Pair(curr.hd+1,curr.node.right));

            }

        }

        for(Map.Entry<Integer,Integer> entry:map.entrySet())

        {

            list.add(entry.getValue());

        }

        return list;

    }

}

import java.util.*;

import java.io.*;

public class Solution{

    static ArrayList<Integer> nextSmallerElement(ArrayList<Integer> arr, int n){

        // Write your code here.

        Stack<Integer> q=new Stack<>();

        q.push(-1);

        int curr=0;

        ArrayList<Integer> al=new ArrayList<>();

        for(int i=n-1;i>=0;i--)

        {

            curr=arr.get(i);

            while(curr<=q.peek())

            {

                q.pop();

            }

            al.add(q.peek());

            q.push(curr);

        }

        Collections.reverse(al);

        return al;

    }

}