Home » Data Structure

Print the path from Root to the given node

In this article, we are going to see how to find the path from the root to the given node, if found?
Submitted by Radib Kar, on August 20, 2020

In this article, we are going to see that given a node how to find the path from the root to that given node? If the given node doesn't exist then print 'Node doesn't exist". In the below example tree,

If the given node is 6,

The path found will be 1->3->5->6

If the given node is 10,

Then the output will be "Node doesn't exist" as we can’t find the given node.

Function rootToNode(TreeNode* node, TreeNode* nodeToFind)
    //base cases
    1)  If current node is NULL
            Return Empty string;
    2)  If the given node is NULL
            Return Empty string;

    Declare final_path="" which will store the root to node path if the node exists;
    if node found in the tree 
        return the path stored in final_path
    otherwise, return an empty string      

To find the node along with storing the path, we use the function rootToNodeRecur(node, "", final_path, nodeToFind)

Function rootToNodeRecur(TreeNode* node,string current_path, string& final_path, TreeNode* nodeToFind):
    1)  if node is NULL
            return false;
    2)  if node is found store the path in final_path & return true
    3)  intermediate path up to now is,  current_path+=string(node->val)+"->";
    4)  If any of the subtrees contain the node return true
        Otherwise 
            return false;
End Function

C++ Implementation:

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

// tree node is defined
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data)
    {
        val = data;
        left = NULL;
        right = NULL;
    }
};

bool rootToNodeRecur(TreeNode* node, string current_path, string& final_path, TreeNode* nodeToFind)
{
    //if node is NULL
    if (!node)
        return false;

    //if node is found store the path in final_path
    if (node->val == nodeToFind->val) {
        final_path = current_path + to_string(nodeToFind->val);
        return true;
    }

    //intermediate path upto now
    current_path += to_string(node->val) + "->";

    //recur for the left subtree
    if (rootToNodeRecur(node->left, current_path, final_path, nodeToFind))
        return true;

    //recur for the right subtree if node not found in the left subtree
    if (rootToNodeRecur(node->right, current_path, final_path, nodeToFind))
        return true;

    //if node not found in both of subtrees then return false
    return false;
}

string rootToNode(TreeNode* node, TreeNode* nodeToFind)
{
    //base cases
    //1.if current node is NULL
    if (!node)
        return "";

    //2. If the given node is NULL
    if (!nodeToFind)
        return "";

    //final_path will store the root to node path if node exists
    string final_path = "";

    //current_path stores intermediate paths
    string current_path = "";

    //if node found in the tree
    //return the path stored in final_path
    //otherwise return empty string
    if (rootToNodeRecur(node, current_path, final_path, nodeToFind))
        return final_path;
    else
        return "";
}

int main()
{
    //building the tree like example 1
    TreeNode* root = new TreeNode(1);

    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->right->left = new TreeNode(5);
    root->right->left->right = new TreeNode(6);

    TreeNode* nodeToFind = new TreeNode(6);
    string path = rootToNode(root, nodeToFind);
    if (path != "")
        cout << "Root to node path is: " << path << endl;
    else
        cout << "Path not found\n";

    nodeToFind = new TreeNode(10);
    path = rootToNode(root, nodeToFind);

    if (path != "")
        cout << "Root to node path is: " << path << endl;
    else
        cout << "Path not found\n";

    return 0;
}

Output:

Root to node path is: 1->3->5->6
Path not found

Dry run with the examples:

Input tree: Tree same as example
Node to Find: 6

In the main we call:
rootToNode(1,"",6)
so call to rootToNode(1,"",6)
The current node is not NULL
Current node value is not the same as the value of the node to find
The intermediate path up to now is "1->"

Recur for its subtrees to find the node

First, we check the left subtree and it will return false 
since we are unable to find the node 6 there

So, recur for the right subtree and if you continue 
the dry run you will find the path "1->3->5->6" 

For the second node with value 10, both the subtrees will return false 
and thus it will return an empty string from the function rootToNode()