[bug] Wrong root hash when keys are removed

[ufoscout]

The root hash calculation returns a wrong value when some keys are removed. This does not happen for all keys. Here is a test that reproduces the bug:

    #[test]
    fn test_insert_and_revert() {
        // Arrange
        let db = Arc::new(MemoryDB::new(true));
        let mut trie = PatriciaTrie::new(db.clone(), Arc::new(HasherKeccak::new()));
        let root_0 = trie.commit().unwrap();

        // Insert "do"
        let root_1 = {
            trie.insert(b"do".to_vec(), b"verb".to_vec()).unwrap();
            trie.root().unwrap()
        };

        // Insert "doge"
        let root_2 = {
            trie.insert(b"doge".to_vec(), b"coin".to_vec()).unwrap();
            trie.root().unwrap()
        };

        // Insert "dog"
        {
            trie.insert(b"dog".to_vec(), b"puppy".to_vec()).unwrap();
            trie.root().unwrap()
        };

        // Remove "dog"
        {
            trie.remove(b"dog").unwrap();
            // It fails here, the root hash does not match the expected one
            assert_eq!(root_2, trie.root().unwrap());
        }

        // Remove "doge"
        {
            trie.remove(b"doge").unwrap();
            assert_eq!(root_1, trie.root().unwrap());
        }

        // Remove "do"
        {
            trie.remove(b"do").unwrap();
            // Now the trie is empty but the hash is not the one of an empty trie
            assert_eq!(root_0, trie.root().unwrap());
        }

    }

[ufoscout]

The bug was introduced by https://github.com/citahub/cita_trie/pull/43 The test succeeds the commit before it