British royal succession order – code

British 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. When you are asked to implement the rule, the algorithm is pretty simple. It is preorder of the hierarchy tree. The first step is to the build the royal succession tree from the parent children relationships. Remember to make the queen as the root of the tree.

Then you can use recursion or stack to preorder the tree. In this implementation, you 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.

What’s the algorithm to get the order of royal succession in coding?

Use Depth first search. Preorder to be precise.

Download RoyalSuccessionOrder.js
Build hierarchy tree – code

Comments are closed