Things to be discussed here,
- Introduction to Tree Queries
- Finding Ancestors
- Explanation with examples
- Implementation in C++
- Practice Problems
Introduction to Tree Queries
In the following article, we will be discussing various techniques to process queries on subtrees and paths of a rooted tree. For example, such queries are:
- What is the kth ancestor of a node?
- What is the sum of values in the subtree of a node?
- What is the sum of value on a path between two nodes?
- what is the lowest common ancestor of two nodes?
Finding Ancestors
The k-th ancestor of a node x in a rooted tree is the node that we will reach if we move k levels up from x. Let ancestor (x,k) denote the kth ancestor of a node x (or 0 if there is no such an ancestor). For example in the following tree ancestor(2,1) = 1 and ancestor(8,2) = 2.
An easy way to calculate any value of ancestor(x,k) is to perform a sequence of k moves in the tree. However, the time complexity of this method is O(k), which may be slow because a tree of n nodes may have a chain of n nodes i.e. linear tree.
An easy way to calculate any value of ancestor(x,k) is to perform a sequence of k moves in the tree. However, the time complexity of this method is O(k), which may be slow because a tree of n nodes may have a chain of n nodes i.e. linear tree.
Simple Approach to find K-th Ancestor
In this type of problem to find the k-th ancestor in rooted tree- First, make an array whose value is the parent of that node.
- Then for any node first ancestor is its parent, 2nd ancestor is parent of a parent, 3rd ancestor is the parent of parent of parent and so own...
- For each node, the time taken will be O(logn).
Implementation in C++
For implementation, take input as a tree rooted at node 1
- In first-line take input n, n - number of nodes in the tree.
- Next n-1 lines take edges u,v.
Practice Problems
That's all for this article in a later article we will be discussing some different approach, in the next session we will be discussing Sub Tree Queries 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 Learn DSA
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 Learn DSA