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

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;
}

You can also try this code with Online C++ Compiler

Run Code

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:

• Path With Minimum Effort
• Unique Paths
• Longest Path In A DAG
   

Recommended Reading:

• Print All Prime Levels of a Binary Tree
• Print all Root Leaf Paths With Their Relative Position
• Print all Root to Leaf Paths with a Maximum Count of Even Nodes
• Print All Nodes That Are at A Distance of K From the Leaf Node
• Print Ancestors of the Given Node
• Palindromic Levels of a Binary Tree
• Tree From Levelorder and Inorder Traversal
   

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!