Some basic probability/expected value, coding question using data structures

1) A pretty number is a number in base 4 whose digits are all either 1 or 0. How many pretty numbers are there < n? 2) Given a list of moves in reversi, return the total number of pieces for each player at the end of the game 3) Trees are given as lists of nodes, where each node is a list with data [key, value, *children), where the order of the children matters. Two trees must be merged (left and right). For a given merged node with the same key between left and right inputs, the merged value should come from the right tree. The list of the merged node's children should start with children from the left tree's child list, and then the leftover right tree's child list. Output (key1,value1,...) in pre-order traversal