Graph Theory Problem Solving - Session 17 ( Subtree & Path Queries)

Things to be discussed here,
  • Tree Traversal Array
  • Subtree Queries
  • Path Queries
  • Practice Problems
Tree Traversal Array
A tree traversal array is an array that contains the nodes of a rooted tree in the order in which a depth-first search from the root node visits them, For example, in the below tree

a depth-first search proceeds as follows
  • 1 -> 2 -> 6  then back to 2 and again back to 1.
  • 1 -> 3 and again back to 1 and so own until it visits all elements.
  • So the order of node visit is 1, 2, 6, 3, 4, 7, 8, 9, 5.
Hence, the tree traversal array is this,
Subtree Queries
Each subtree of a tree corresponds to a subarray of the tree traversal array such that the first element of the subarray is the root node. For example, the following subarray contains the nodes of the subtree of the node 4,
Using this fact, we can efficiently process queries that are related to the subtrees of a tree. As an example, consider a problem where each node is assigned a value and our task is to support the following queries:
  • Update the value of a node
  • Calculate the sum of values in the subtree of a node
To understand this problem better, let us take the above tree and assign some value to each node. The values are written in red color.
For example, the sum of the subtree of node 4 is 3+4+3+1 = 11.

Now to solve this type of problem, the general idea is to construct a tree traversal array that contains three values for each node, the node value, the size of the subtree with this node as root, and the value of the node. For the above tree the array is as follows:

Using this array, we can calculate the sum of the values in a subtree by first finding out the size of the subtree and then the values of the corresponding nodes. For example, the values in the subtree of node 4 can be found as follows. 

And to answer these queries faster we can use Binary Indexed Tree or Segment Tree. After which we can update and findSum in O(logn) time complexity.

Path Queries
Using a tree traversal array, we can also efficiently calculate sums of values on paths from the root node to any node of the tree. Consider a problem where our task is to support the following queries:
  • Change the value of the node
  • Calculate the sum of values on a path from the root to the node.
For example in the following tree, the sum of values from the root node to node 7 is 4+5+5 = 14
We can solve this problem like before, but now each value in the last row of the array is the sum of values on a path from the root to the node. For example, the following array corresponds to the above tree:

When the value of a node increases by x, the sums of all nodes in its subtree increase by x. For example, if the value of node 4 increases by 1, the array changes as follows:

Thus, to support both update all the values in a range and retrieve a single value. This can be done in O(logn) time using a binary indexed or segment tree.

That's all for this article, implementation is left upon you and if you face problems then do ask us we will add the code also. we will be discussing the  Lowest Common Ancestor and problems related to it and for now practice problems. ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).

If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by CODELABS3277


Post a Comment