lca in tree

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class LCABruteForce {

    // Helper function to find path from root to given node
    public static boolean findPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        if (root == null) return false;

        path.add(root); // Add current node to path

        if (root == target) return true;
        // Recur left or right
        if (findPath(root.left, target, path) || findPath(root.right, target, path))
            return true;

        // If not found, backtrack
        path.remove(path.size() - 1);
        return false;
    }

    // Main LCA function using path comparison
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path1 = new ArrayList<>();
        List<TreeNode> path2 = new ArrayList<>();

        // Find paths from root to p and q
        if (!findPath(root, p, path1) || !findPath(root, q, path2)) {
            return null; // If either node is not present
        }

        // Compare the paths to find the last common node
        int i = 0;
        while (i < path1.size() && i < path2.size()) {
            if (path1.get(i) != path2.get(i)) break;
            i++;
        }

        return path1.get(i - 1); // Last common node
    }

    // Example Usage
    public static void main(String[] args) {
        /*
              3
             / \
            5   1
           / \ / \
          6  2 0  8
            / \
           7   4
        */
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        TreeNode p = root.left; // 5
        TreeNode q = root.left.right.right; // 4

        TreeNode lca = lowestCommonAncestor(root, p, q);
        System.out.println("LCA of " + p.val + " and " + q.val + " is: " + lca.val);
    }
}