given any two nodes of a tree, you want to find if these two nodes has parent child relationship, how to do it in O(1) time and O(n) space

given any two nodes of a tree, you want to find if these two nodes has parent child relationship, how to do it in O(1) time and O(n) space

use pre-order to traverse the tree, for each node, record the start time and finish time, building a hash table for these recodes. if the time interval of one node includes the time interval of the second node, they have parent child relationship.