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

//! Balanced Binary Tree Check (Generic, Production-Grade)
//!
//! Checks if a binary tree is height-balanced.
//!
//! # Type Parameters
//! * `T`: Node value type. Must implement `Clone`.
//!
//! # Example
//! ```rust
//! use pofk_algorithm::tree_algorithms::binary_tree_traversal::TreeNode;
//! use pofk_algorithm::tree_algorithms::balanced_tree::*;
//! let root = Some(Box::new(TreeNode::new(1)));
//! let balanced = is_balanced(&root);
//! ```
use crate::tree_algorithms::binary_tree_traversal::TreeNode;

pub fn is_balanced<T: Clone>(root: &Option<Box<TreeNode<T>>>) -> bool {
    fn helper<T: Clone>(node: &Option<Box<TreeNode<T>>>) -> Option<usize> {
        match node {
            Some(n) => {
                let l = helper(&n.left)?;
                let r = helper(&n.right)?;
                if l > r + 1 || r > l + 1 {
                    None
                } else {
                    Some(1 + l.max(r))
                }
            }
            None => Some(0),
        }
    }
    helper(root).is_some()
}