Royal succession order – code

Royal succession order is also known as the line of succession to the British throne. Under common law, the crown is inherited by a sovereign’s children or by a childless sovereign’s nearest collateral line. You can get the current British monarchy succession order here.

As programmer, you might be asked to implement the rule using a program language. The algorithm is pretty simple – it is pre-order of the hierarchy tree. The first step is to the build the hierarchy tree from the parent children relationships. Please refer to this post to construct the hierarchy tree. Remember to make the queen as the root of the tree.

Then we can use recursion or stack to pre-order the tree. In this implementation, we use stack to hold royal members. Staring from the root, push the member in the stack. In a while loop, pop the member in the stack and add him/her to the order list. Meanwhile, push this member’s successors (from the last to the first) to the stack. Finally return the order list.

Google Interview Question:
Given the monarchy relatiohship, as list of “parent child1, child2”

implement its method to get the list of successors in order.
Order of Succession: king -> a1 -> b1 -> d1 -> d2 -> b2 -> d3 -> a2 -> c1 -> c2




The royal succession sequence:
[Queen, Charles, William, George, Charlotte, Louis, Harry, Archie, Andrew, Beatric, Eugenie, Edward, James, Louise, Anne, Peter, Savannah, Isla, Zara, Mia, Lena]

O Notation:
Time complexity: O(n)
Space complexity: O(n)
n is number of monarchy members.

Download RoyalSuccessionOrder.js

Comments are closed