Question:
Given a binary tree root node, get the deepest left leaf node
Example:
Consider the image given below and its mirror.
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