static ArrayList<Integer> verticalOrder(Node root) {
    TreeMap<Integer, ArrayList<Integer>> map = new TreeMap<>();
    ArrayList<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Queue<Pair> queue = new LinkedList<>();
    queue.add(new Pair(root, 0));

    while (!queue.isEmpty()) {
        Pair temp = queue.poll();
        Node current = temp.node;
        int hd = temp.hd;

        map.putIfAbsent(hd, new ArrayList<>());
        map.get(hd).add(current.data);

        if (current.left != null) queue.add(new Pair(current.left, hd - 1));
        if (current.right != null) queue.add(new Pair(current.right, hd + 1));
    }

    for (ArrayList<Integer> vertical : map.values()) {
        result.addAll(vertical);
    }

    return result;
}

static class Pair {
    Node node;
    int hd;

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

static int preIndex = 0;

public static Node buildTree(int[] inorder, int[] preorder) {
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    preIndex = 0;
    return buildTreeHelper(preorder, inorder, 0, inorder.length - 1, inorderMap);
}

private static Node buildTreeHelper(int[] preorder, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inorderMap) {
    if (inStart > inEnd) return null;

    int rootValue = preorder[preIndex++];
    Node root = new Node(rootValue);

    int inorderIndex = inorderMap.get(rootValue);

    root.left = buildTreeHelper(preorder, inorder, inStart, inorderIndex - 1, inorderMap);
    root.right = buildTreeHelper(preorder, inorder, inorderIndex + 1, inEnd, inorderMap);

    return root;
}

ArrayList<Integer> preOrder(Node root) {
    ArrayList<Integer> list = new ArrayList<>();
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        
        list.add(node.data);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    
    return list;
}

public static ArrayList<Integer> inOrder(Node root) {
    ArrayList<Integer> list = new ArrayList<>();
    Stack<Node> stack = new Stack<>();
    Node current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        list.add(current.data);

        current = current.right;
    }

    return list;
}

public static ArrayList<Integer> postOrder(Node root) {
    ArrayList<Integer> list = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Stack<Node> stack = new Stack<>();
    Stack<Node> output = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node current = stack.pop();
        output.push(current);

        if (current.left != null) {
            stack.push(current.left);
        }
        if (current.right != null) {
            stack.push(current.right);
        }
    }

    while (!output.isEmpty()) {
        list.add(output.pop().data);
    }

    return list;
}

public static int findMax(Node root) {
    if (root == null) {
        return Integer.MIN_VALUE;
    }

    int leftMax = findMax(root.left);
    int rightMax = findMax(root.right);

    return Math.max(root.data, Math.max(leftMax, rightMax));
}


public static int findMin(Node root) {
    if (root == null) {
        return Integer.MAX_VALUE;
    }

    int leftMin = findMin(root.left);
    int rightMin = findMin(root.right);

    return Math.min(root.data, Math.min(leftMin, rightMin));
}

static int canRepresentBST(int[] preorder, int N) {
    Stack<Integer> stack = new Stack<>();
    
    int min = Integer.MIN_VALUE;
    
    for (int i = 0; i < N; i++) {
        if (preorder[i] < min) {
            return 0;
        }

        while (!stack.isEmpty() && stack.peek() < preorder[i]) {
            min = stack.pop();
        }

        stack.push(preorder[i]);
    }

    return 1;
}

boolean areMirror(Node left, Node right) {
    if (left == null && right == null) {
        return true;
    }

    if (left == null || right == null) {
        return false;
    }

    return (left.data == right.data) 
           && areMirror(left.left, right.right) 
           && areMirror(left.right, right.left);
}

public boolean isTree(int n, int m, ArrayList<ArrayList<Integer>> edges) {
    // A tree with n nodes must have exactly n-1 edges
    if (m != n - 1) {
        return false;
    }
    
    // Create an adjacency list
    ArrayList<Integer> adj[] = new ArrayList[n];
    for (int i = 0; i < n; i++) {
        adj[i] = new ArrayList<>();
    }
    
    // Populate the adjacency list with the given edges
    for (ArrayList<Integer> edge : edges) {
        int u = edge.get(0);
        int v = edge.get(1);
        adj[u].add(v);
        adj[v].add(u);
    }
    
    // To keep track of visited nodes
    boolean[] visited = new boolean[n];
    
    // Perform DFS to check connectivity and cycles
    if (hasCycle(adj, visited, 0)) {
        return false;
    }
    
    // Check if all nodes are visited (i.e., the graph is connected)
    for (boolean nodeVisited : visited) {
        if (!nodeVisited) {
            return false; // Not all nodes are visited, so the graph is not connected
        }
    }
    
    // If no cycles and all nodes are visited, it is a tree
    return true;
}

// Helper function to perform DFS and detect cycles
private boolean hasCycle(ArrayList<Integer> adj[], boolean[] visited, int start) {
    Stack<int[]> stack = new Stack<>();
    stack.push(new int[]{start, -1}); // Starting node with no parent
    
    while (!stack.isEmpty()) {
        int[] current = stack.pop();
        int node = current[0];
        int parent = current[1];
        
        if (visited[node]) {
            continue; // Skip if node is already visited
        }
        
        visited[node] = true;
        
        // Explore all neighbors
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                stack.push(new int[]{neighbor, node}); // Push neighbor with current node as parent
            } else if (neighbor != parent) {
                // If an adjacent node is visited and is not the parent, it's a cycle
                return true;
            }
        }
    }
    
    return false; // No cycle detected
}

public static Node deleteNode(Node root, int X) {
    if (root == null) {
        return null;
    }

    if (X < root.data) {
        root.left = deleteNode(root.left, X);
    }
    else if (X > root.data) {
        root.right = deleteNode(root.right, X);
    }
    
    else {
        // Case 1: Node has no children (leaf node)
        if (root.left == null && root.right == null) {
            return null;
        }
        // Case 2: Node has one child
        else if (root.left == null) {
            return root.right;
        }
        else if (root.right == null) {
            return root.left;
        }
        // Case 3: Node has two children
        else {
            Node inorderSuccessor = minValueNode(root.right);
            root.data = inorderSuccessor.data;
            root.right = deleteNode(root.right, inorderSuccessor.data);
        }
    }

    return root;
}

private static Node minValueNode(Node node) {
    Node current = node;
    while (current.left != null) {
        current = current.left;
    }
    return current;
}

public static boolean isSubtree(Node T, Node S) {
    if (S == null) {
        return true;
    }

    if (T == null) {
        return false;
    }

    if (isIdentical(T, S)) {
        return true;
    }

    return isSubtree(T.left, S) || isSubtree(T.right, S);
}

private static boolean isIdentical(Node r1, Node r2) {
    if (r1 == null && r2 == null) {
        return true;
    }

    if (r1 == null || r2 == null || r1.data != r2.data) {
        return false;
    }

    return isIdentical(r1.left, r2.left) && isIdentical(r1.right, r2.right);
}

static class Result {
    int size;
    boolean isBST;
    int min;
    int max;
    
    public Result(int size, boolean isBST, int min, int max) {
        this.size = size;
        this.isBST = isBST;
        this.min = min;
        this.max = max;
    }
}

static int largestBst(Node root) {
    return largestBstUtil(root).size;
}

static Result largestBstUtil(Node node) {
    // Base case: If the node is null, it's a valid BST with size 0
    if (node == null) {
        return new Result(0, true, Integer.MAX_VALUE, Integer.MIN_VALUE);
    }
    
    // Recursively find the largest BST in the left and right subtrees
    Result leftResult = largestBstUtil(node.left);
    Result rightResult = largestBstUtil(node.right);
    
    // If the current node is a valid BST:
    // 1. The left subtree is a BST and its maximum value is less than the current node's value.
    // 2. The right subtree is a BST and its minimum value is greater than the current node's value.
    if (leftResult.isBST && rightResult.isBST && node.data > leftResult.max && node.data < rightResult.min) {
        // The current node forms a valid BST, calculate the size
        int size = leftResult.size + rightResult.size + 1;
        // Update the min and max values for this subtree
        int min = Math.min(node.data, leftResult.min);
        int max = Math.max(node.data, rightResult.max);
        // Return the result for this subtree
        return new Result(size, true, min, max);
    } else {
        // If not a BST, return the size of the largest BST found in either left or right subtree
        return new Result(Math.max(leftResult.size, rightResult.size), false, 0, 0);
    }
}

public static void findPreSuc(Node root, Node[] pre, Node[] suc, int key) {
    // Base case: if root is null, there's no predecessor or successor
    if (root == null) {
        return;
    }
    
    // If key is smaller than root's data, move to the left subtree
    if (key < root.data) {
        suc[0] = root;  // Successor is the current node
        findPreSuc(root.left, pre, suc, key);  // Recurse on left subtree
    }
    // If key is larger than root's data, move to the right subtree
    else if (key > root.data) {
        pre[0] = root;  // Predecessor is the current node
        findPreSuc(root.right, pre, suc, key);  // Recurse on right subtree
    }
    // If key is equal to root's data, we've found the node
    else {
        // Find the predecessor (max value in the left subtree)
        if (root.left != null) {
            Node temp = root.left;
            while (temp.right != null) {
                temp = temp.right;  // Move to the rightmost node in the left subtree
            }
            pre[0] = temp;  // This is the predecessor
        }
        
        // Find the successor (min value in the right subtree)
        if (root.right != null) {
            Node temp = root.right;
            while (temp.left != null) {
                temp = temp.left;  // Move to the leftmost node in the right subtree
            }
            suc[0] = temp;  // This is the successor
        }
    }
}

boolean isIsomorphic(Node root1, Node root2) {
    if (root1 == null && root2 == null) {
        return true;
    }

    if (root1 == null || root2 == null) {
        return false;
    }

    return (root1.data == root2.data) &&
           ((isIsomorphic(root1.left, root2.left) && isIsomorphic(root1.right, root2.right)) ||
            (isIsomorphic(root1.left, root2.right) && isIsomorphic(root1.right, root2.left)));
}

ArrayList<Integer> zigZagTraversal(Node root) {
	ArrayList<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);

    boolean leftToRight = false;

    while (!queue.isEmpty()) {
        int size = queue.size();
        ArrayList<Integer> currentLevel = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            Node currentNode = queue.poll();
            currentLevel.add(currentNode.data);

            if (currentNode.left != null) {
                queue.offer(currentNode.left);
            }

            if (currentNode.right != null) {
                queue.offer(currentNode.right);
            }
        }

        if (leftToRight) {
            Collections.reverse(currentLevel);
        }

        result.addAll(currentLevel);
        leftToRight = !leftToRight;
    }

    return result;
}

public static int isSumProperty(Node root) {
    if (root == null || (root.left == null && root.right == null)) {
        return 1;
    }

    int leftSum = (root.left != null) ? root.left.data : 0;
    int rightSum = (root.right != null) ? root.right.data : 0;

    if (root.data == leftSum + rightSum &&
        isSumProperty(root.left) == 1 &&
        isSumProperty(root.right) == 1) {
        return 1;
    }

    return 0;
}

public static ArrayList<ArrayList<Integer>> Paths(Node root) {
    ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
    if (root == null) return paths;
    
    Stack<Node> stack = new Stack<>();
    Stack<ArrayList<Integer>> pathStack = new Stack<>();
    
    stack.push(root);
    pathStack.push(new ArrayList<>(List.of(root.data))); // Start with the root node's data
    
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        ArrayList<Integer> path = pathStack.pop();
        
        // If it's a leaf node, add the current path to the result
        if (node.left == null && node.right == null) {
            paths.add(new ArrayList<>(path)); // Make a copy of the path
        }
        
        // Traverse left subtree if available
        if (node.left != null) {
            stack.push(node.left);
            ArrayList<Integer> leftPath = new ArrayList<>(path);
            leftPath.add(node.left.data);  // Add left child to the path
            pathStack.push(leftPath);
        }
        
        // Traverse right subtree if available
        if (node.right != null) {
            stack.push(node.right);
            ArrayList<Integer> rightPath = new ArrayList<>(path);
            rightPath.add(node.right.data); // Add right child to the path
            pathStack.push(rightPath);
        }
    }
    
    Collections.reverse(paths);
    
    return paths;
}

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

public int KthSmallestElement(Node root, int K) {
    int[] count = new int[1];
    int[] result = new int[1];
    
    result[0] = -1;
    
    inOrderTraversal(root, K, count, result);
    
    return result[0];
}

private void inOrderTraversal(Node node, int k, int[] count, int[] result) {
    if (node == null || count[0] >= k) {
        return;
    }
    
    inOrderTraversal(node.left, k, count, result);
    
    count[0]++;
    
    if (count[0] == k) {
        result[0] = node.data;
        return;
    }
    
    inOrderTraversal(node.right, k, count, result);
}

static ArrayList<ArrayList<Integer>> levelOrder(Node root) {
    ArrayList<ArrayList<Integer>> levels = new ArrayList<>();
    if (root == null) return levels;
    
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        ArrayList<Integer> currentLevel = new ArrayList<>();
        
        for (int i = 0; i < levelSize; i++) {
            Node node = queue.poll();
            currentLevel.add(node.data);
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        
        levels.add(currentLevel);
    }
    
    return levels;
}

static ArrayList<Integer> levelOrder(Node root) {
    ArrayList<Integer> bfs = new ArrayList<>();
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        Node current = queue.poll();
        bfs.add(current.data);
        
        if (current.left != null) queue.offer(current.left);
        if (current.right != null) queue.offer(current.right);
    }

    return bfs;
}

public int kthAncestor(Node root, int k, int node) {
    if (root == null) return -1;

    // Map to store parent pointers
    Map<Integer, Integer> parentMap = new HashMap<>();
    parentMap.put(root.data, -1); // Root has no parent

    // BFS to populate parentMap
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        Node current = queue.poll();

        if (current.left != null) {
            parentMap.put(current.left.data, current.data);
            queue.offer(current.left);
        }

        if (current.right != null) {
            parentMap.put(current.right.data, current.data);
            queue.offer(current.right);
        }
    }

    // Trace back k ancestors
    int current = node;
    while (k > 0 && current != -1) {
        current = parentMap.get(current);
        k--;
    }

    // If k > 0, the kth ancestor does not exist
    return current;
}

int findCeil(Node root, int key) {
    if (root == null) return -1;
    int ceil = -1;
    
    while (root != null) {
        if (root.data == key) {
            return root.data;
        } else if (key < root.data) {
            ceil = root.data;
            root = root.left;
        } else {
            root = root.right;
        }
    }

    return ceil;
}

public int sumOfLongRootToLeafPath(Node root) {
    int[] result = new int[2]; // result[0] = maxDepth, result[1] = maxSum
    findLongestPath(root, 0, 0, result);
    return result[1];
}

private void findLongestPath(Node node, int depth, int sum, int[] result) {
    if (node == null) {
        // Update maxDepth and maxSum if necessary
        if (depth > result[0]) {
            result[0] = depth;
            result[1] = sum;
        } else if (depth == result[0] && sum > result[1]) {
            result[1] = sum;
        }
        return;
    }

    // Include the current node's value in the sum
    sum += node.data;

    // Recur for left and right subtrees
    findLongestPath(node.left, depth + 1, sum, result);
    findLongestPath(node.right, depth + 1, sum, result);
}

static int floor(Node root, int key) {
    if (root == null) return -1;
    int floor = -1;
    
    while (root != null) {
        if (root.data == key) {
            return root.data;
        } else if (key > root.data) {
            floor = root.data;
            root = root.right;
        } else {
            root = root.left;
        }
    }

    return floor;
}

String serialize(Node root) {
    if (root == null) return "N";
        
    String leftSubtree = serialize(root.left);
    String rightSubtree = serialize(root.right);
        
    return root.data + ";L" + leftSubtree + ";R" + rightSubtree;
}

int dupSub(Node root) {
    if (root == null) return 0;
        
    Queue<Node> queue = new LinkedList<>();
    HashSet<String> subtrees = new HashSet<>();
        
    queue.offer(root);
        
    while (!queue.isEmpty()) {
        Node node = queue.poll();
            
        String subtree = serialize(node);
            
        if (node.left == null && node.right == null) {
            continue;
        }
            
        if (subtrees.contains(subtree)) {
            return 1;
        }
            
        subtrees.add(subtree);
            
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
        
    return 0;
}