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

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

Here is my code to use range minimal query to resolve the LCA problem. Applied comments from here (Using range minimal query for lowest common ancestor (LCA) ), since it is new code, I start a new thread.

More specifically, my questions are:

Major ideas of my idea are:

Source code in Python 2.7,

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])

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

Major ideas of my idea are:

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])