C++ Program to Find Deepest Left Leaf in a Binary Tree

Hello friends! In this article, You will know the topic about “C++ Program to Find Deepest Left Leaf in a Binary Tree“. Without wasting our valuable time, Jump on to the article directly.

C++ Program to Find Deepest Left Leaf in a Binary Tree

C++ Program to Find Deepest Left Leaf in a Binary Tree

Program Code

/* 
 * C++ program to Find Deepest Left Leaf in a Binary Tree
 */
#include <cstdio>
#include <iostream>
using namespace std;
 
/* 
 * Node Declaration
 */ 
struct Node
{
    int val;
    Node *left, *right;
};
/* 
 * create new node
 */ 
Node *newNode(int data)
{
    Node *temp = new Node;
    temp->val = data;
    temp->left = temp->right =  NULL;
    return temp;
}
 
/* 
 * find deepest leaf node
 */ 
void deepestLeftLeafUtil(Node *root, int lvl, int *maxlvl, bool isLeft, Node **resPtr)
{
    if (root == NULL)
        return;
    if (isLeft && !root->left && !root->right && lvl > *maxlvl)
    {
        *resPtr = root;
        *maxlvl = lvl;
        return;
    }
    deepestLeftLeafUtil(root->left, lvl + 1, maxlvl, true, resPtr);
    deepestLeftLeafUtil(root->right, lvl + 1, maxlvl, false, resPtr);
}
/* 
 * implement deepestLeftLeafUtil.
 */  
Node* deepestLeftLeaf(Node *root)
{
    int maxlevel = 0;
    Node *result = NULL;
    deepestLeftLeafUtil(root, 0, &maxlevel, false, &result);
    return result;
}
 
/* 
 * Main
 */  
int main()
{
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->left = newNode(5);
    root->right->right = newNode(6);
    root->right->left->right = newNode(7);
    root->right->right->right = newNode(8);
    root->right->left->right->left = newNode(9);
    root->right->right->right->right = newNode(10);
    Node *result = deepestLeftLeaf(root);
    if (result)
        cout << "The deepest left child is " << result->val;
    else
        cout << "There is no left leaf in the given tree";
    return 0;
}

Conclusion

I hope this article helps you to learn “C++ Program to Find Deepest Left Leaf in a Binary Tree“. If you face any issues please let me know via the comment section. Share this article with other C/C++ developers via social networks.

Share on:

Hi, I'm Ranjith a full-time Blogger, YouTuber, Affiliate Marketer, & founder of Coding Diksha. Here, I post about programming to help developers.

Leave a Comment