Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Prerequisites
1.2.
Problem Statement
1.3.
Sample Example
2.
Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is a Binary Tree?
3.2.
What is root node?
3.3.
What is a leaf node?
4.
Conclusion
Last Updated: Mar 27, 2024

Print path from root to a given node in a binary tree

Author Anju Jaiswal
1 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

In this blog we will discuss the problem, i.e., " Print path from root to a given node in a binary tree,".It is highly asked in product-based companies. We'll go over all the steps of the solution.

Let's get started with the problem statement without further ado.

Prerequisites

Knowledge of trees and related terminologies such as recursiontrees, and the main traversals inorderpreorderpostorder are common prerequisites for every tree problem. It is not advisable to proceed to the Print path from root to a given node in a binary tree without mastering these fundamental methods and data structures.

Nonetheless, we'll try to go through every detail needed to Print path from root to a given node in a binary tree.

Problem Statement

Given a binary tree with different nodes (There are no two nodes with the same data values as the other node). Here the problem is to print the path from root to a given node n. If node n is absent, print "No Path is present for node n."

Sample Example

Example 1:

Input: 

n = 4

 

Output: 

Print path from root to a given node in a binary tree : root node to node 4
4->7->9

 

Example 2:

Input: 

n = 4

Output: 

Print path from root to a given node in a binary tree : root node to node 4
No Path is present from root node to node 4

Approach

Create a recursive function that searches the binary tree for the needed node by traversing the various paths. If node n is present, it returns true and accumulates the path nodes in some vector. Else it returns false.

Pseudocode

  • If the root is NULL, return FALSE.
  • If the root is not NULL, push the root's data into a vector for storing the path.
  • if root->data = n, return TRUE.
  • If node n is present in the root-> left or root-> right subtree, return TRUE.
  • Else remove root-> data value from vector for storing the path.
  • And return FALSE.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
class node
{
    public:
    int data;
    node* left;
    node* right;
};

node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;

    return(Node);
}

bool Path_from_root_to_a_given_node(node *root, vector<int>& path, int n)
{
    // if root is NULL
    // there is no path
    if (!root)
       return false;
    

    path.push_back(root->data);

    if (root->data == n)
       return true;
    

    if (Path_from_root_to_a_given_node(root->left, path, n) ||
       Path_from_root_to_a_given_node(root->right, path, n))
       return true;
    
    
    path.pop_back();
    return false;        
}


int main()
{
    // binary tree formation
    node *root = newNode(4);
    root->left = newNode(5);
    root->right = newNode(7);
    root->left->right = newNode(1);
    root->left->right->left = newNode(8);
    root->left->right->right = newNode(2);
    root->right->left = newNode(9);
    root->right->right = newNode(6);
    root->right->left->right = newNode(3);

       
    int n = 9;
    cout<<"Print path from root to a given node in a binary tree : root node to node "<< n <<endl;
    vector<int> path;
    bool ans = Path_from_root_to_a_given_node(root, path, n);
       if (ans)
    {
       for (int i=0; i<path.size()-1; i++)
           cout << path[i] << "->";
       cout<<n<<endl;
    
    }
    
    // 'n' is not present in the binary tree
    else
       cout << "No Path is present from root node to node "<<n<<endl;
    return 0;
}

 

Output:

Print path from root to a given node in a binary tree : root node to node 9
4->7->9

 

Complexity Analysis

Time Complexity: o(n)

O(1) in the best case when the root node is the required node.

O(n)  in the worst case, where n is the number of nodes in the binary tree.

Space Complexity: o(n)

For storing the path from root node to node n.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a Binary Tree?

Each node can have a maximum of two children in a binary tree. Because the binary designation implies 'two,' each node can have either zero, one, or two children.

What is root node?

The root node is the highest node in the tree structure, and has no parent.

What is a leaf node?

A node with two empty subtrees is called a leaf node.

Conclusion

This article discussed how to Print path from root to a given node in a binary tree, with examples and their C++ code.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Recommended Problems:

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Print all possible N-nodes Full Binary Trees
Next article
Find the Maximum Path Sum Between Two Leaves of A Binary Tree
Live masterclass