algorithms_edu/algo/graph/tree/
height.rs

1//! # Tree height Example
2//!
3//! - Time Complexity: O(n)
4//!
5//! # Resources
6//!
7//! - [W. Fiset's video](https://www.youtube.com/watch?v=0qgaIMqOEVs&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=8)
8
9use super::{BinaryTreeNode, Node};
10
11impl Node {
12    pub fn height(&self) -> usize {
13        self.children
14            .iter()
15            .fold(0, |height, child| std::cmp::max(height, child.height() + 1))
16    }
17}
18
19impl BinaryTreeNode {
20    pub fn height(&self) -> usize {
21        match (&self.left, &self.right) {
22            (None, None) => 0,
23            (Some(node), None) | (None, Some(node)) => node.height() + 1,
24            (Some(l), Some(r)) => std::cmp::max(l.height(), r.height()) + 1,
25        }
26    }
27}
28
29#[cfg(test)]
30mod tests {
31    use super::*;
32
33    #[test]
34    fn test_tree_height() {
35        //         6
36        //      2  7  8
37        //    1  3
38        //  0   4 5
39        let root = Node {
40            id: 6,
41            children: vec![
42                Node {
43                    id: 2,
44                    children: vec![
45                        Node {
46                            id: 1,
47                            children: vec![Node::new(0)],
48                        },
49                        Node {
50                            id: 3,
51                            children: vec![Node::new(4), Node::new(5)],
52                        },
53                    ],
54                },
55                Node::new(7),
56                Node::new(8),
57            ],
58        };
59        assert_eq!(root.height(), 3);
60        let node_2 = &root.children[0];
61        assert_eq!(node_2.height(), 2);
62        let node_7 = &root.children[1];
63        assert_eq!(node_7.height(), 0);
64    }
65    #[test]
66    fn test_binary_tree_height() {
67        //        0
68        //       / \
69        //      1   2
70        //     / \ / \
71        //    3  4 5  6
72        //   / \
73        //  7   8
74        let tree = BinaryTreeNode {
75            id: 0,
76            left: Some(Box::new(BinaryTreeNode {
77                id: 1,
78                left: Some(Box::new(BinaryTreeNode {
79                    id: 3,
80                    left: Some(Box::new(BinaryTreeNode::new(7))),
81                    right: Some(Box::new(BinaryTreeNode::new(8))),
82                })),
83                right: Some(Box::new(BinaryTreeNode::new(4))),
84            })),
85            right: Some(Box::new(BinaryTreeNode {
86                id: 2,
87                left: Some(Box::new(BinaryTreeNode::new(5))),
88                right: Some(Box::new(BinaryTreeNode::new(6))),
89            })),
90        };
91
92        let singleton_height = BinaryTreeNode::new(5).height();
93        println!("Singleton height: {}", singleton_height);
94        assert_eq!(singleton_height, 0);
95
96        let tree_height = tree.height();
97        println!("Tree height: {}", tree.height());
98        assert_eq!(tree_height, 3);
99    }
100}
algorithms_edu/algo/graph/tree/height.rs

algorithms_edu/algo/graph/tree/
height.rs
