C++ Coding Test Course, Lowest Common Ancestor

Hello! In this lecture, we will discuss one of the concepts that often appears in coding tests, ‘Lowest Common Ancestor’. This lecture focuses on learning how to solve problems using C++. First, I will explain what the lowest common ancestor is and detail the algorithms to find it.

1. Problem Description

We will address the problem of finding the lowest common ancestor of two nodes when given a binary tree. The nodes in a binary tree have a parent-child relationship, and each node has a unique value.

Problem Definition

Given a binary tree and two nodes A and B, write a function that finds and returns the lowest common ancestor of A and B.

Input Format

Binary Tree: The root node of the tree is provided.
Two Nodes A and B: Both nodes are valid nodes within the tree.

Output Format

Returns the lowest common ancestor of nodes A and B. If there is no common ancestor, return nullptr.

Example Input

Example Output

Lowest Common Ancestor: 5 (A: 5, B: 1)

2. Algorithm Approaches

There are two main approaches commonly used to find the lowest common ancestor:

Recursive Method
Storing Parent Nodes to Search Indirectly

2.1. Recursive Approach

The most common method is to start at the root of the tree and explore recursively. When both nodes are in the left or right subtree of the current node, continue exploring that subtree. If the current node finds A or B, return that node; if both nodes are found, return the current node.

2.2. Parent Storing Method

This method involves storing the parent information of each node. It finds the common ancestor indirectly by following the parent information of the two nodes. However, this method requires additional memory.

3. C++ Code Implementation

Below is the C++ code for finding the lowest common ancestor.

#include 
using namespace std;

// Definition of the binary tree node
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Function to find the lowest common ancestor
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // Base case: return root if it's nullptr or is p or q
    if (root == nullptr || root == p || root == q) {
        return root;
    }

    // Search for the lowest common ancestor in the left and right subtrees
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);

    // If both left and right subtrees found a node, return the current node
    if (left != nullptr && right != nullptr) {
        return root; // Current node is the lowest common ancestor
    }

    // Return the ancestor from one of the subtrees if found
    return left != nullptr ? left : right;
}

// Main function
int main() {
    // Create a binary tree
    TreeNode *root = new TreeNode(3);
    TreeNode *n1 = new TreeNode(5);
    TreeNode *n2 = new TreeNode(1);
    TreeNode *n3 = new TreeNode(6);
    TreeNode *n4 = new TreeNode(2);
    TreeNode *n5 = new TreeNode(0);
    TreeNode *n6 = new TreeNode(8);
    TreeNode *n7 = new TreeNode(7);
    TreeNode *n8 = new TreeNode(4);

    root->left = n1;
    root->right = n2;
    n1->left = n3;
    n1->right = n4;
    n2->left = n5;
    n2->right = n6;
    n4->left = n7;
    n4->right = n8;

    // Call to find the lowest common ancestor
    TreeNode* ancestor = lowestCommonAncestor(root, n1, n2);
    cout << "Lowest Common Ancestor: " << ancestor->val << endl;

    return 0;
}

4. Code Explanation

The above code implements a method to find the lowest common ancestor of two nodes A and B in a binary tree. Now, let me explain each part.

4.1. TreeNode Structure

The TreeNode structure defines a node in a binary tree. Each node includes an integer value and pointers to the left and right child nodes.

4.2. lowestCommonAncestor Function

Handles the base case: returns the current node if it’s nullptr or if it’s A or B.
Searches for the lowest common ancestor in the left and right subtrees.
If a node is found in both left and right subtrees, it returns the current node.
If found in only one subtree, it returns the ancestor from that subtree.

4.3. Main Function

It creates a binary tree and includes a call to search for the lowest common ancestor of the specified nodes A and B. The result is printed to the console.

5. Complexity Analysis

The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree. In the worst case, all nodes may need to be checked.

The space complexity is O(H), where H is the height of the binary tree. In the worst case, the stack depth can be equal to the depth of the tree.

6. Conclusion

In this lecture, we covered the lowest common ancestor problem. This problem frequently appears in various algorithm questions related to binary trees, so it is important to understand and practice it thoroughly. Solving additional problems can be a good method to enhance your understanding.

Thank you! In the next lecture, we will cover another interesting algorithm topic. If you have any questions or feedback, please leave them in the comments.