Query Processing on Tree

I want to Know how one can convert a tree into an array and find Sub-tree of any node…I have gone through one of the blog which discuss about it but not able to get What are 3 arrays discover[],begin[] ,and end[]. The code which describe about Starting time i.e IN[] array and finishing time i.e OUT[] array ,I am familiar with that. It will be great help if someone explain me his method to convert a tree to an array or explain what the 3 arrays are used for with an example.

here is the blog.Thanks in Advance !!!

Formally, that’s called the euler tour technique. Basically it just lists down nodes in DFS order (ie. preorder traversal), so that you can perform a whole subtree operation from node u via a “range query” on begin[u] to end[u]. Essentially:

discover[] - the nodes in preorder traversal

begin[] - the IN[] array; the time when you discovered the node (entered the DFS)

end[] - the OUT[] array; the time when you leave the node (exited the DFS)

You build the query tree on the discover[] array, for example a BIT or a segment tree since it’s the one holding the nodes in DFS order. You can also associate any value in the discover[] array, depending on the problem. Hope that helps your understanding.

1 Like