<commit_before>public class JavaDistanceTwoNodesInBinaryTree {
    // Change to true to debug
    private static final boolean DEBUG = false;

    public static class Node {
        int value;
        Node left;
        Node right;

        private Node(int value) {
            this.value = value;
        }
    }

    // Find the Lowest Common Ancestor (LCA) of the two nodes which the distance is being measured
    private static Node findLCA(Node root, int n1, int n2) {
        // Check edge condition if root is null
        if (root == null) {
            return null;
        }

        // Check if reach either n1 or n2, then return the root which is one of the branches of the LCA
        if ((root.value == n1) || (root.value == n2)) {
            return root;
        }

        Node leftBranchCheck = findLCA(root.left, n1, n2);
        Node rightBranchCheck = findLCA(root.right, n1, n2);

        // Check if found both n1 and n2 exists in leftCheck and rightCheck return values,
        //   then root has the LCA
        if ((leftBranchCheck != null) && (rightBranchCheck != null)) {
            if (DEBUG) {
                System.out.println("Found LCA = " + root.value);
            }
            return root;
        }

        // Recurse down left tree if LCA of both nodes still in left tree, else LCA of both is still down right tree
        if (leftBranchCheck != null) {
            return findLCA(root.left, n1, n2);
        } else {
            return findLCA(root.right, n1, n2);
        }
    }

    // Get the level (distance from root) to any given value in the binary tree
    private static int getLevel(Node root, int searchValue, int currLevel) {
        // Check if passing in edge condition
        if (root == null) {
            return -1;
        }

        // Check if now reached the value being searched
        if (root.value == searchValue) {
            return currLevel;
        }

        // Get the left tree distance to the searchValue.  If left does not have the value, the level will be -1
        int leftLevel = getLevel(root.left, searchValue, currLevel + 1);

        // If left tree does not have the searchValue, it must be in the right tree
        if (leftLevel == -1) {
            return getLevel(root.right, searchValue, currLevel + 1);
        }

        // It wasn't in right tree, so return the left tree distance
        return leftLevel;
    }

    private static int findDistance(Node root, int n1, int n2) {
        Node lcaNode = findLCA(root, n1, n2);
        if (DEBUG) {
            System.out.println("LCA of: " + n1 + ":" + n2 + " is = " + lcaNode.value);
        }

        int distN1fromLCA = getLevel(lcaNode, n1, 0);
        int distN2fromLCA = getLevel(lcaNode, n2, 0);

        return distN1fromLCA + distN2fromLCA;
    }

    // Driver program to test above functions
    public static void main(String[] args) {

        // Let us create binary tree given in
        // the above example
        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);<commit_msg>Added comment to point to new image of test case #01.<commit_after>public class JavaDistanceTwoNodesInBinaryTree {
    // Change to true to debug
    private static final boolean DEBUG = false;

    public static class Node {
        int value;
        Node left;
        Node right;

        private Node(int value) {
            this.value = value;
        }
    }

    // Find the Lowest Common Ancestor (LCA) of the two nodes which the distance is being measured
    private static Node findLCA(Node root, int n1, int n2) {
        // Check edge condition if root is null
        if (root == null) {
            return null;
        }

        // Check if reach either n1 or n2, then return the root which is one of the branches of the LCA
        if ((root.value == n1) || (root.value == n2)) {
            return root;
        }

        Node leftBranchCheck = findLCA(root.left, n1, n2);
        Node rightBranchCheck = findLCA(root.right, n1, n2);

        // Check if found both n1 and n2 exists in leftCheck and rightCheck return values,
        //   then root has the LCA
        if ((leftBranchCheck != null) && (rightBranchCheck != null)) {
            if (DEBUG) {
                System.out.println("Found LCA = " + root.value);
            }
            return root;
        }

        // Recurse down left tree if LCA of both nodes still in left tree, else LCA of both is still down right tree
        if (leftBranchCheck != null) {
            return findLCA(root.left, n1, n2);
        } else {
            return findLCA(root.right, n1, n2);
        }
    }

    // Get the level (distance from root) to any given value in the binary tree
    private static int getLevel(Node root, int searchValue, int currLevel) {
        // Check if passing in edge condition
        if (root == null) {
            return -1;
        }

        // Check if now reached the value being searched
        if (root.value == searchValue) {
            return currLevel;
        }

        // Get the left tree distance to the searchValue.  If left does not have the value, the level will be -1
        int leftLevel = getLevel(root.left, searchValue, currLevel + 1);

        // If left tree does not have the searchValue, it must be in the right tree
        if (leftLevel == -1) {
            return getLevel(root.right, searchValue, currLevel + 1);
        }

        // It wasn't in right tree, so return the left tree distance
        return leftLevel;
    }

    private static int findDistance(Node root, int n1, int n2) {
        Node lcaNode = findLCA(root, n1, n2);
        if (DEBUG) {
            System.out.println("LCA of: " + n1 + ":" + n2 + " is = " + lcaNode.value);
        }

        int distN1fromLCA = getLevel(lcaNode, n1, 0);
        int distN2fromLCA = getLevel(lcaNode, n2, 0);

        return distN1fromLCA + distN2fromLCA;
    }

    // Driver program to test above functions
    public static void main(String[] args) {

        // Let us create binary tree given in
        // the test case #01 example: See: JavaDistanceTwoNodesInBinaryTreeTestcase01.png
        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);
{'fraction_non_alphanumeric': 0.088715953307393, 'fraction_numerical': 0.0133852140077821, 'mean_word_length': 1.882907133243607, 'pattern_counts': {'":': 2, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3866057', 'n_tokens_mistral': 1861, 'n_tokens_neox': 1827, 'n_words': 711}