Home » Data Structure

Find All Root to Leaf Paths in an N-array Tree

In this article, we are going to discuss how to find all root to leaf paths in an n-array tree?
Submitted by Radib Kar, on July 31, 2020

Prerequisite: N-array Tree

In the above example, all the root to leaf paths are:

[1->2->6->15]
[1->2->6->16]
[1->2->6->17]
[1->2->6->18]
[1->2->6->19]
Etcs.

We can find all root to leaf paths by depth-first search traversals.

The algorithm is:

We will store the path as a string, so each path will be each string and to store the paths as a string of vector.

void  all_root_to_leaf(TreeNode root, string current_path, vector<string> paths)
    if(root is a leaf)
        Append the root value to string current_path
        Add current_path to the vector
    End if
	 
    Append the root value to string current_path
    for each child of this root:
        Recursively call the function all_root_to_leaf(child, current_path, paths)
    End for
End Function

Below is the implementation for the above algorithm:

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    vector<TreeNode*> children;
    TreeNode(int v)
    {
        val = v;
    }
    TreeNode(int v, int n)
    {
        val = v;
        children = vector<TreeNode*>(n, NULL);
    }
};

//recursive function to find all store to leaf paths
void all_root_to_leaf_paths(TreeNode* root, string s, vector<string>& paths)
{
    if (!root)
        return;
    //leaf node
    if (root->children.size() == 0) {
        //append root->val to the current path
        s += to_string(root->val);
        paths.push_back(s);
        return;
    }

    s += to_string(root->val) + "->";

    for (int i = 0; i < root->children.size(); i++) {
        all_root_to_leaf_paths(root->children[i], s, paths);
    }
}

int main()
{
    TreeNode* root = new TreeNode(1, 4);
    
    root->children[0] = new TreeNode(2, 3);
    root->children[1] = new TreeNode(3, 1);
    root->children[2] = new TreeNode(4, 2);
    root->children[3] = new TreeNode(5, 3);

    root->children[0]->children[0] = new TreeNode(6, 5);
    root->children[0]->children[1] = new TreeNode(7);
    root->children[0]->children[2] = new TreeNode(8);

    root->children[1]->children[0] = new TreeNode(9);

    root->children[2]->children[0] = new TreeNode(10);
    root->children[2]->children[1] = new TreeNode(11);

    root->children[3]->children[0] = new TreeNode(12);
    root->children[3]->children[1] = new TreeNode(13);
    root->children[3]->children[2] = new TreeNode(14, 1);

    root->children[0]->children[0]->children[0] = new TreeNode(15);
    root->children[0]->children[0]->children[1] = new TreeNode(16);
    root->children[0]->children[0]->children[2] = new TreeNode(17);
    root->children[0]->children[0]->children[3] = new TreeNode(18);
    root->children[0]->children[0]->children[4] = new TreeNode(19);

    root->children[3]->children[2]->children[0] = new TreeNode(20);
    vector<string> paths;
    all_root_to_leaf_paths(root, "", paths);

    cout << "All root to leaf paths are:\n";
    for (auto it : paths)
        cout << it << "\n";

    return 0;
}

Output:

All root to leaf paths are:
1->2->6->15
1->2->6->16
1->2->6->17
1->2->6->18
1->2->6->19
1->2->7
1->2->8
1->3->9
1->4->10
1->4->11
1->5->12
1->5->13
1->5->14->20

To show how this is working, we can dry-run up to a few steps.

We define vector<string> arr
So at the main function, we call all_root_to_leaf_paths (root, "", arr)
So call to   all_root_to_leaf_paths (1, "", arr)
------------------------------------------------

all_root_to_leaf_paths(1, "", arr)
it's not NULL
It's not a leaf node
Append root->val to current path("")
So current path now "1"+"->"
Now for each child, 
we will call all_root_to_leaf_paths(child of 1, "1", arr)
Say for example the child is 2, 
so it will call all_root_to_leaf_paths(2, "1->", arr)
------------------------------------------------

all_root_to_leaf_paths(2, "1->", arr)
it's not NULL
It's not a leaf node
Append root->val to current path("1->")
So current path now "1"+"->"+"2"+"->"
Now for each child, 
we will call all_root_to_leaf_paths(child of 2, "1", arr)
Say for example the child is 6, 
so it will call all_root_to_leaf_paths(6, "1->2->", arr)
------------------------------------------------

all_root_to_leaf_paths(6, "1->2->", arr)
it's not NULL
It's not a leaf node
Append root->val to current path("1->2->")
So current path now "1->2->6->"
Now for each child 
we will call all_root_to_leaf_paths(child of 6, "1->2->6->", arr)
Say for example the child is 6, 
so it will call all_root_to_leaf_paths(15, "1->2->6->", arr)
------------------------------------------------

all_root_to_leaf_paths(15, "1->2->6->", arr)
it's not NULL
It's a leaf node
Append root->val to current path("1->2->6->")
So current path now "1->2->6->15"

Since it's the leaf node, we add the current path to vector<string> arr and return. Remember we passed a reference to the vector so it will store all the paths.  

In this way, after performing all the recursion we will have all the root to leaf paths stored.