Bits and binary trees

Edit distance between Big and Bang ●○○○○ 10 ptsGiven two strings $\text{str}_1 = \text{"Big"}$ and $\text{str}_2 = \text{"Bang"}$ , find the minimum number of operations needed to convert $\text{str}_1$ into $\text{str}_2$ . The allowed operations are deleting a character, replacing a character with another, and inserting a character at any position.
Element without a duplicate ●○○○○ 10 ptsEvery element of the list $2, 2, 3, 4, 5, 9, 5, 4, 9, 1, 3$ appears exactly twice except one element, which appears only once. Find the element that does not have a duplicate.
Locating a single bit error ●●○○○ 20 ptsA binary code $x_1x_2\ldots x_7$ satisfies the parity check equations $x_4\oplus x_5\oplus x_6\oplus x_7=0$ , $x_2\oplus x_3\oplus x_6\oplus x_7=0$ and $x_1\oplus x_3\oplus x_5\oplus x_7=0$ , where $\oplus$ is addition modulo 2. A code of this type was changed to $1101101$ after a bit error occurred at only one position $k$ during communication, so the bit at position $k$ flipped. Find $k$ .
Count unival subtrees in a tree ●●○○○ 20 ptsA unival subtree of a binary tree is a subtree in which all nodes have the same value. A single leaf counts as a unival subtree. Consider the following binary tree. The root has value $0$ . The root's left child has value $1$ and is a leaf. The root's right child has value $0$ ; its left child has value $1$ and its right child has value $0$ (a leaf). The node with value $1$ (the left child of the right child) has two children, both with value $1$ (leaves). How many unival subtrees does the tree have?

More in Counting principles

Counting in lists and arrays Counting principle Handshakes Integer pairs with bounded product Licence plates Numbers and codes with digit rules Numbers containing a digit Numbers from digit cards Outfits and selections Parity and odd sums Stacking blocks Vowels and consonants Words and strings with restrictions