Deepest left leaf node in a Binary Tree

Given a Binary Tree, find the deepest leaf node that is left child of its parent. For example, consider the following tree. The deepest left leaf node is the node with value 9.

       1
     /   \
    2     3
  /      /  \  
 4      5    6
        \     \
         7     8
        /       \
       9         10

We strongly recommend you to minimize the browser and try this yourself first.

The idea is to recursively traverse the given binary tree and while traversing, maintain “level” which will store the current node’s level in the tree. If current node is left leaf, then check if its level is more than the level of deepest left leaf seen so far. If level is more then update the result. If current node is not leaf, then recursively find maximum depth in left and right subtrees, and return maximum of the two depths. Thanks to Coder011 for suggesting this approach.

// A C++ program to find the deepest left leaf in a given binary tree

#include <stdio.h>

#include <iostream>

using namespace std;

 

struct Node

{

    int val;

    struct Node *left, *right;

};

 

Node *newNode(int data)

{

    Node *temp = new Node;

    temp->val = data;

    temp->left = temp->right =  NULL;

    return temp;

}




// A utility function to find deepest leaf node. // lvl: level of current node. // maxlvl: pointer to the deepest left leaf node found so far // isLeft: A bool indicate that this node is left child of its parent // resPtr: Pointer to the result void deepestLeftLeafUtil(Node *root, int lvl, int *maxlvl, bool isLeft, Node **resPtr) { // Base case if (root == NULL) return; // Update result if this node is left leaf and its level is more // than the maxl level of the current result if (isLeft && !root->left && !root->right && lvl > *maxlvl) { *resPtr = root; *maxlvl = lvl; return; } // Recur for left and right subtrees deepestLeftLeafUtil(root->left, lvl+1, maxlvl, true, resPtr); deepestLeftLeafUtil(root->right, lvl+1, maxlvl, false, resPtr); } // A wrapper over deepestLeftLeafUtil(). Node* deepestLeftLeaf(Node *root) { int maxlevel = 0; Node *result = NULL; deepestLeftLeafUtil(root, 0, &maxlevel, false, &result); return result; }

 

// Driver program to test above function 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; }

Output:

The deepest left child is 9

Time Complexity: The function does a simple traversal of the tree, so the complexity is O(n).