ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Get deepest Left Leaf Node in Binary Tree

prodevelopertutorial October 8, 2020

Question:

Given a binary tree root node, get the deepest left leaf node

Example:

Consider the image given below and its mirror.

binary_tree

From the above image, node 7 is the deepest left leaf node.

Solution in C++

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

int currentLevel;
Node *deepest_left_leaf_node;

void get_deepest_left_leaf_node(Node *node, int level, bool is_left_leaf) 
{
    if (node == NULL) 
    {
      return;
    }

    if (is_left_leaf && node->left == NULL && node->right == NULL && level > currentLevel) {
      deepest_left_leaf_node = node;
      currentLevel = level;
    }

    get_deepest_left_leaf_node(node->left, level + 1, true);
    get_deepest_left_leaf_node(node->right, level + 1, false);
  }


int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    get_deepest_left_leaf_node(root, 1, false);

    cout<<"The deepest left leaf node is "<<deepest_left_leaf_node->data<< endl;

    return 0;  
}  

Output:

The deepest left leaf node is 7

 

Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2020 ProDeveloperTutorial.com
Get top courses from: Educative.io