pofk_algorithm 0.0.3

A collection of efficient algorithms implemented in Rust for real-world projects.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

//! Lowest Common Ancestor (LCA) in Binary Tree (Generic, Production-Grade)
//!
//! Finds the lowest common ancestor of two nodes in a binary tree.
//!
//! # Type Parameters
//! * `T`: Node value type. Must implement `Clone` + `Eq`.
//!
//! # Example
//! ```rust
//! use pofk_algorithm::tree_algorithms::binary_tree_traversal::TreeNode;
//! use pofk_algorithm::tree_algorithms::lowest_common_ancestor::*;
//! let root = Some(Box::new(TreeNode::new(1)));
//! let lca = lowest_common_ancestor(&root, &2, &3);
//! ```
use crate::tree_algorithms::binary_tree_traversal::TreeNode;

pub fn lowest_common_ancestor<T: Clone + Eq>(
    root: &Option<Box<TreeNode<T>>>,
    p: &T,
    q: &T,
) -> Option<T> {
    fn helper<T: Clone + Eq>(
        node: &Option<Box<TreeNode<T>>>,
        p: &T,
        q: &T,
    ) -> Option<T> {
        if let Some(n) = node {
            if &n.val == p || &n.val == q {
                return Some(n.val.clone());
            }
            let left = helper(&n.left, p, q);
            let right = helper(&n.right, p, q);
            match (left, right) {
                (Some(_l), Some(_r)) => Some(n.val.clone()),
                (Some(l), None) => Some(l),
                (None, Some(r)) => Some(r),
                (None, None) => None,
            }
        } else {
            None
        }
    }
    helper(root, p, q)
}