rust99/binary-trees/P56/src/lib.rs at master · sameer-hashflow/rust99 · GitHub

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
use bintree::Tree;
use std::fmt;

pub fn is_symmetric<T: fmt::Display>(tree: &Tree<T>) -> bool {
    fn is_mirror_of<T: fmt::Display>(t1: &Tree<T>, t2: &Tree<T>) -> bool {
        match (t1, t2) {
            (Tree::End, Tree::End) => true,
            (Tree::End, Tree::Node { .. }) => false,
            (Tree::Node { .. }, Tree::End) => false,
            (
                Tree::Node {
                    value: _,
                    left: lleft,
                    right: lright,
                },
                Tree::Node {
                    value: _,
                    left: rleft,
                    right: rright,
                },
            ) => is_mirror_of(lleft, rright) && is_mirror_of(lright, rleft),
        }
    }

    match tree {
        Tree::Node {
            value: _,
            left,
            right,
        } => is_mirror_of(left, right),
        Tree::End => true,
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_is_symmetric_end() {
        assert_eq!(is_symmetric(&Tree::<char>::end()), true);
    }

    #[test]
    fn test_is_symmetric_leaf() {
        assert_eq!(is_symmetric(&Tree::leaf('a')), true);
    }

    #[test]
    fn test_is_symmetric() {
        assert_eq!(
            is_symmetric(&Tree::node('a', Tree::leaf('b'), Tree::leaf('c'))),
            true
        );

        assert_eq!(
            is_symmetric(&Tree::node('a', Tree::leaf('b'), Tree::end())),
            false
        );

        assert_eq!(
            is_symmetric(&Tree::node('a', Tree::end(), Tree::leaf('c'))),
            false
        );
    }

    #[test]
    fn test_is_symmetric_complex() {
        let tree = Tree::node(
            'a',
            Tree::node(
                'b',
                Tree::node('d', Tree::end(), Tree::leaf('e')),
                Tree::end(),
            ),
            Tree::node(
                'c',
                Tree::end(),
                Tree::node('f', Tree::leaf('g'), Tree::end()),
            ),
        );
        assert_eq!(is_symmetric(&tree), true);

        let tree = Tree::node(
            'a',
            Tree::node('b', Tree::leaf('d'), Tree::leaf('e')),
            Tree::node(
                'c',
                Tree::end(),
                Tree::node('f', Tree::leaf('g'), Tree::end()),
            ),
        );
        assert_eq!(is_symmetric(&tree), false);
    }
}