Java Coding Test Course, Lowest Common Ancestor

Problem Definition

                3
              /   \
             5     1
            / \   / \
           6   2 0   8
              / \
             7   4
        

Problem Solution

1. Problem Analysis

To find the lowest common ancestor of two nodes in the given binary tree, two conditions must be satisfied:

• There must exist a node B that is an ancestor of node A.
• There must also exist a node B that is an ancestor of node C.

To establish this relationship, we can traverse the binary tree while tracking the parent node for each node.

2. Algorithm Design

First, to find a specific node in the binary tree, we can use search techniques such as DFS (Depth First Search) or BFS (Breadth First Search).

The specific algorithm to find the lowest common ancestor is as follows:

1. Start traversing the tree from the root node.
2. Find the given two nodes in both subtrees.
3. If one node is found in each subtree, the current node is the lowest common ancestor.
4. If neither is found, return null.

3. Java Code Implementation

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class LCA {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case
        if (root == null || root == p || root == q) {
            return root;
        }

        // Find LCA in the left and right subtrees.
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // If both are found, current node is the LCA.
        if (left != null && right != null) {
            return root;
        }

        // Return the result from the subtree where one was found.
        return left != null ? left : right;
    }
}
    

4. Code Explanation

The key points in the above code are as follows:

• Recursively check if the current node is null or the node we are looking for.
• Find the lowest common ancestor in the left and right subtrees, and return the current node if both are found.
• Finally, if found only in one subtree, return that node; otherwise, return null.

5. Time Complexity

The time complexity of this algorithm is O(N), as each node in the collection is visited once. N is the number of nodes in the tree.

6. Space Complexity

The space complexity is O(H), where H is the height of the tree. In the worst case, if the binary tree is skewed to one side, the maximum height can be N.

Practical Code Test

To test the problem in practice, let’s create an example tree and write code to find the LCA.

public class Main {
    public static void main(String[] args) {
        // Creating the binary tree
        TreeNode root = new TreeNode(3);
        TreeNode node5 = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node6 = new TreeNode(6);
        TreeNode node2 = new TreeNode(2);
        TreeNode node0 = new TreeNode(0);
        TreeNode node8 = new TreeNode(8);
        TreeNode node7 = new TreeNode(7);
        TreeNode node4 = new TreeNode(4);

        root.left = node5;
        root.right = node1;
        node5.left = node6;
        node5.right = node2;
        node1.left = node0;
        node1.right = node8;
        node2.left = node7;
        node2.right = node4;

        // Create an object to find the LCA
        LCA lcaFinder = new LCA();
        TreeNode lca = lcaFinder.lowestCommonAncestor(root, node5, node1);
        System.out.println("LCA of 5 and 1: " + lca.val); // Output: 3

        lca = lcaFinder.lowestCommonAncestor(root, node5, node4);
        System.out.println("LCA of 5 and 4: " + lca.val); // Output: 5
    }
}
    

Conclusion

In this article, we covered the problem of finding the lowest common ancestor in a binary tree, explaining the problem definition, algorithm design, Java code implementation, and code testing. This problem can be applied in various situations and is very helpful for understanding the basic concepts of algorithms and data structures.

Through this, you can learn useful algorithm patterns for preparing for coding tests in Java and contribute to improving your problem-solving skills.