Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem statement 
1.2.
Sample Examples
2.
Naive Approach
3.
Efficient Approach
3.1.
Steps of algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
Is it possible for a binary tree to have only one child?
4.2.
In a binary tree, how do you count the number of nodes?
4.3.
How to recognise a leaf node in a binary tree?
5.
Conclusion
Last Updated: Mar 27, 2024

Print the Longest Path from the Root to Leaf in a Binary Tree

Author Mehak Goel
4 upvotes
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Binary Trees are popular Data Structures and have a wide range of applications throughout various fields. Binary Trees are also important when it comes to interviews with top tech companies. A mastery of Binary Trees could help us solve a lot of problems. In this article, we are going to take a look at one such problem.

Problem statement 

We are given a Binary tree. Our goal is to print the longest path from the root node to the leaf node in a Binary tree. If there are multiple paths, print any one of them.

Sample Examples

Example 1:

 

 

Output: 

5 -> 9 -> 12 

 

Explanation:

Longest paths from the root node to the leaf node are:  

5 -> 9 -> 12 

5 -> 9 -> 4

5 -> 10 -> 8 

We can print any of them.

 

Example 2:

 

 

Output:

18 -> 12 -> 10 -> 7

Naive Approach

In this approach, we will generate all the possible paths from the root node to all leaf nodes in the binary tree. We will keep track of the maximum length path and finally print it.

Time complexity: O(n^2)

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

Efficient Approach

In this approach, we will be using recursion to solve the problem.

First, we will get the longest path from the left and right subtrees recursively. Then, we will add the root node to one with the longer path. 

Thus, we will get the longest path from the root node to the leaf node.

Steps of algorithm

  • If the given root node is null then no path of the binary tree exists, hence we will return an empty vector.
  • We will get the longest path from the left subtree in leftvector by recursively traversing root -> left.
  • Similarly, we will get the longest path from the right subtree in rightvector by recursively traversing root -> right.
  • In the end, we will compare both the sizes of the rightvector and the leftvector. Then, we will add the root node to the longer size and return that particular vector.
  • Print the vector in reverse order as we need the longest path from the root to the leaf node.

Implementation in C++

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

struct Node {
    int value;
    Node *left;
    Node  *right;
};
 
struct Node* newNode(int value)
{
    struct Node* node = new Node;
    node->value = value;
    node->left = node->right = NULL;
 
    return (node);
}
 
// Function to get and return the longest path
vector<int> longestPath(Node* root)
{
 
    // If root node is null, no binary tree exists so we return an empty vector
    if (root == NULL) {
        vector<int> temp = {};
        return temp;
    }
   
    // Recursive call on left subtree
    vector<int> leftvector = longestPath(root->left);
 
    // Recursive call on right subtree
    vector<int> rightvector = longestPath(root->right);
 
    // Compare the sizes of the two vectors and add current node 

    if (rightvector.size() > leftvector.size())
        rightvector.push_back(root->value);

    else
        leftvector.push_back(root->value);
 
    // Return the vector
    return (leftvector.size() > rightvector.size() ? leftvector : rightvector);
}
 

int main()
{
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->right = newNode(4);
    root->left->left = newNode(5);
    root->left->right->left = newNode(6);
    root->left->right->left->right = newNode(7);

    vector<int> output = longestPath(root);
    int n = output.size();
 
    cout << output[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        cout << " -> " << output[i];
    }
 
    return 0;
}

 

Output:

1 -> 2 -> 4 -> 6 -> 7

 

Complexity Analysis

Time complexity: O(n), where n is the number of nodes in the given tree as we are traversing all the nodes.

Space complexity: O(h), where h is the height of the given binary tree.

Frequently Asked Questions

Is it possible for a binary tree to have only one child?

A binary tree is a tree in which no node has more than two children, and each child is either a right or left child, even if it is the parent's only child. A full binary tree is the one with two children for each internal node.

In a binary tree, how do you count the number of nodes?

Return the value of (2^height – 1) as the resultant count of nodes if the left and right heights of the given Tree are equal to the current root value. Otherwise, call the function for the left and right subtrees recursively and return the sum + 1 as the resultant node count.

How to recognise a leaf node in a binary tree?

Steps in C++:
- If root==NULL, return.
- If root->left==NULL and root->right==NULL, it is a leaf node, print the node data.
- Repeat the process for both the left and the right subtree.

 

Conclusion

This article discussed the approach to print the longest path from the root to the leaf node in a Binary tree with examples for a better understanding of the problem and its C++ code.

Recommended Problems:

Recommended Reading:

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Thank you for reading!

Previous article
How to Find the Maximum Value of Bitwise AND from Root to Leaf in a Binary tree?
Next article
Print the node values at odd levels of a Binary tree
Live masterclass