Using range minimal query for lowest common ancestor (LCA) -- part 2

Question

Here is my code to use range minimal query to resolve the LCA problem. I applied comments from here.

Any advice on code bugs, performance improvement in terms of algorithm time complexity, code style are appreciated.

Major ideas of my idea are:

1. Build depth array of each node by in-order traverse
2. Build MRQ index for depth array built in first step
3. For any two nodes, their LCA are the lowest depth node between them (in depth array)

from collections import defaultdict
class TreeNode:
 def __init__(self, value, left, right):
 self.value = value
 self.left = left
 self.right = right
 def in_order_traverse(self, result, depth, node_index_map):
 if self.left:
 self.left.in_order_traverse(result, depth+1, node_index_map)
 result.append((depth, self.value))
 node_index_map[self.value] = len(result) - 1
 if self.right:
 self.right.in_order_traverse(result, depth+1, node_index_map)
class RMQ:
 def __init__(self, raw_array):
 self.rmq_index = defaultdict(tuple)
 step = 0
 for i,v in enumerate(raw_array):
 self.rmq_index[(i, step)] = v
 step += 1
 while 2 ** (step-1) <= len(raw_array):
 for i,v in enumerate(raw_array):
 if i+2**(step-1) < len(raw_array) and self.rmq_index[(i+2**(step-1), step-1)][0] < self.rmq_index[(i, step-1)][0]:
 self.rmq_index[(i,step)] = self.rmq_index[(i+2**(step-1), step-1)]
 else:
 self.rmq_index[(i,step)] = self.rmq_index[(i, step-1)]
 step += 1
 def rmq_query(self, i, j):
 step = 0
 while i + 2 ** step - 1 < j:
 step += 1
 step -= 1
 x = self.rmq_index[(i,step)]
 y = self.rmq_index[(j-2**step+1, step)]
 if x[0] < y[0]:
 return x[1]
 else:
 return y[1]
if __name__ == "__main__":
 root = TreeNode(1, TreeNode(2, TreeNode(4, None, None), TreeNode(5, None, None)), TreeNode(3, TreeNode(6, None, None),TreeNode(7,None,None)))
 result = []
 node_index_map = defaultdict(int)
 root.in_order_traverse(result, 0, node_index_map)
 rmq = RMQ(result)
 print rmq.rmq_query(node_index_map[4], node_index_map[5])
 print rmq.rmq_query(node_index_map[4], node_index_map[7])

• George McGinn: I'm researching your question, but I need to know how much different is your question from this one before I spend tons of time on it? [codereview.stackexchange.com/questions/42408/…

Answer 1

advice on ... code style

Including docstrings would be good, e.g. to spell out that RMQ denotes Range Minimal Query. But as a more pressing matter, your identifiers are much too ambiguous. The names rmq_index or node_index_map are just not helpful as you never describe an index, and result and raw_array are even worse. At least stick to one or the other, don't use both of them to describe the same thing. Not once did you refer to the literature (e.g. Schieber and Vishkin), nor comment on an invariant you were maintaining.

It would be helpful to include sample in/out values in the SO posting or, better, in the comments or docstrings. You regrettably ignored the advice to use flake8.

 self.value = value

This appears to be more of a unique id than some continuous value.

 for i,v in enumerate(raw_array):

This may have been clearer as for i, depth_id.

It's not clear how a step is different from a depth.

In ... self.rmq_index[(i+2**(step-1), step-1)][0] < self.rmq_index[(i, step-1)][0]: it would have been helpful to break out depth_left & depth_right and compare them.

These look like they are useful tests:

print rmq.rmq_query(node_index_map[4], node_index_map[5])
print rmq.rmq_query(node_index_map[4], node_index_map[7])

but they would be far more informative in the form of assertEqual statements in a unittest.TestCase.