In this article, we will take a detailed look at the definition and solutions of the Lowest Common Ancestor (LCA) problem.
Problem Definition
Problem: Lowest Common Ancestor (LCA)
Find the lowest common ancestor of two nodes in a binary tree. The lowest common ancestor is the ancestor of both nodes and is the closest node to both nodes.
For example, given the following binary tree:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
The lowest common ancestor of node 5 and node 1 is 3, and the lowest common ancestor of node 5 and node 4 is 5.
Input Format
- The root node of the binary tree and two nodes are given.
Output Format
- Print the lowest common ancestor of the given two nodes.
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:
- Start traversing the tree from the root node.
- Find the given two nodes in both subtrees.
- If one node is found in each subtree, the current node is the lowest common ancestor.
- 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.