Closest neighbour in BST

//Closest neighbour in BST

import java.io.*;
import java.util.*;
import java.util.LinkedList;
import java.util.Queue;

class Node {
    int key;
    Node left;
    Node right;

    Node(int x) {
        this.key = x;
        left = null;
        right = null;
    }
}

class GfG {

    static Node buildTree(String str) {

        if(str.length() == 0 || str.charAt(0) == 'N') {
            return null;
        }

        String ip[] = str.split(" ");
        Node root = new Node(Integer.parseInt(ip[0]));
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        int i = 1;

        while(queue.size() > 0 && i < ip.length) {
            Node currNode = queue.peek();
            queue.remove();
            String currVal = ip[i];

            if(!currVal.equals("N")) {
                currNode.left = new Node(Integer.parseInt(currVal));
                queue.add(currNode.left);
            }

            i++;

            if(i >= ip.length) {
              break;
            }

            currVal = ip[i];

            if(!currVal.equals("N")) {
                currNode.right = new Node(Integer.parseInt(currVal));
                queue.add(currNode.right);
            }
            i++;
        }

        return root;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        while(t > 0) {
            String s = br.readLine();
            int N = Integer.parseInt(br.readLine());
            Node root = buildTree(s);
            Solution g = new Solution();
            System.out.println(g.findMaxForN(root, N));
            t--;
        }
    }
}

class Node {
    int key;
    Node left, right;

    Node(int x) {
        key = x;
        left = right = null;
    }
}

class Solution {
    public static int findMaxForN(Node root, int n) {
        if(root == null) {
            return -1;
        }
        
        if(root.key == n) {
            return n;
        }
 
        else if(root.key < n) {
            int k = findMaxForN(root.right, n);
            
            if (k == -1) {
                return root.key;
            }
            
            else {
                return k;
            }
        } 
 
        else if(root.key > n) {
            return findMaxForN(root.left, n);
        }
        
        return -1;
    }
}