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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
use super::{BinaryTreeNode, Node};
impl Node {
pub fn height(&self) -> usize {
self.children
.iter()
.fold(0, |height, child| std::cmp::max(height, child.height() + 1))
}
}
impl BinaryTreeNode {
pub fn height(&self) -> usize {
match (&self.left, &self.right) {
(None, None) => 0,
(Some(node), None) | (None, Some(node)) => node.height() + 1,
(Some(l), Some(r)) => std::cmp::max(l.height(), r.height()) + 1,
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_tree_height() {
let root = Node {
id: 6,
children: vec![
Node {
id: 2,
children: vec![
Node {
id: 1,
children: vec![Node::new(0)],
},
Node {
id: 3,
children: vec![Node::new(4), Node::new(5)],
},
],
},
Node::new(7),
Node::new(8),
],
};
assert_eq!(root.height(), 3);
let node_2 = &root.children[0];
assert_eq!(node_2.height(), 2);
let node_7 = &root.children[1];
assert_eq!(node_7.height(), 0);
}
#[test]
fn test_binary_tree_height() {
let tree = BinaryTreeNode {
id: 0,
left: Some(Box::new(BinaryTreeNode {
id: 1,
left: Some(Box::new(BinaryTreeNode {
id: 3,
left: Some(Box::new(BinaryTreeNode::new(7))),
right: Some(Box::new(BinaryTreeNode::new(8))),
})),
right: Some(Box::new(BinaryTreeNode::new(4))),
})),
right: Some(Box::new(BinaryTreeNode {
id: 2,
left: Some(Box::new(BinaryTreeNode::new(5))),
right: Some(Box::new(BinaryTreeNode::new(6))),
})),
};
let singleton_height = BinaryTreeNode::new(5).height();
println!("Singleton height: {}", singleton_height);
assert_eq!(singleton_height, 0);
let tree_height = tree.height();
println!("Tree height: {}", tree.height());
assert_eq!(tree_height, 3);
}
}