Find Descendant in Tree Data Structure
A tree data structure is a type of data structure that is used to organize data in a hierarchical format. Trees are typically composed of nodes, each of which contains data and links to other nodes in the tree.
One of the most common ways to traverse a tree is by finding the descendants of a given node. A descendant of a node is any node which is below the given node in the tree structure. This means that any child, grandchild, great-grandchild, and so on, of the given node are considered descendants.
To find the descendants of a node, one must start at the node and traverse the tree, following each link to the next node in the structure. The easiest way to find the descendants of a node is to use a breadth-first search (BFS) algorithm. This algorithm works by starting at the given node and then visiting each of its children in order.
As each child is visited, its children are then visited in order, and so on. This continues until all of the descendants of the given node have been visited. Another way to find the descendants of a node is to use a depth-first search (DFS) algorithm.
The simplest way to find a descendant is to start at the given node and then traverse down the tree until the desired descendant is found. This approach, however, can be inefficient if the tree is large.
A better approach is to use a recursive algorithm. In this approach, the algorithm starts at the given node and then visits each of its children in turn. For each child, it then checks to see if the desired descendant is present; if so, the search is successful.
If not, it then visits each of the child's children and repeats the process until the desired descendant is found.
Java pseudo code where we can find the descendent in a tree data structure
function findDescendants (node)
{
let descendants = [ ];
if (node. children. length === 0)
{
return descendants;
}
for (let i = 0; i < node. children. length; i ++)
{
descendants. push (node. children [ i]);
descendants = descendants. concat (findDescendants (node. children [ i]));
}
return descendants;
}
Finding the Descendent of tree data structure by Recursive Approach
// Recursive method to print all the descendants of a given node
public void printDescendants (Node root)
{
if (root == null)
return;
// Print all the descendants of root
for (int i = 0; i < root. children. size ( ); i ++)
{
printDescendants (root. children. get ( i));
System. out. println (root. children. get (i). data);
}
}
Program to find the descendent of a tree data structure in java language
//This program prints the descendants of a given node in a tree.
import java. util. *;
public class DescendantTree
{
// Tree node class static
class Node
{
int data;
Node left, right;
Node (int data)
{
this. data = data;
left = null;
right = null;
}
}
static Node root;
// function to print the descendants of a given node
static void printDescendants (Node node)
{
// if node is NULL return
if (node == null)
return;
// if left child is not null print it
if (node. left != null)
System. out. print (node. left. data + " ");
// if right child is not null print it
if (node. right != null)
System. out. print (node. right. data + " ");
// recurse over the left and right sub trees of that corresponding root node.
printDescendants (node. left);
printDescendants (node. right);
}
// Driver code
public static void main (String [ ] args)
{
root = new Node (10);
root. left = new Node (20);
root. right = new Node (30);
root. left. left = new Node (40);
root. left. right = new Node (50);
root. right. left = new Node (60);
root. right. right = new Node (70);
System. out. print (" Descendants of Node 1: " );
printDescendants (root);
}
}
OUTPUT:
Descendants of Node 10: 40 50 60 70
In this way we can find the descendants of a particular node of the tree data structure. The above code is for the recursive approach.