Deepest left leaf node in a binary tree

Here given code implementation process.
/*
C Program
Deepest left leaf node in a binary tree
*/
#include <stdio.h>
#include <stdlib.h>
// Tree Node
struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
struct TreeNode *root;
};
// Create new tree
struct BinaryTree *newTree()
{
// Create dynamic node
struct BinaryTree *tree = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
//return new tree
return tree;
}
// returns a new node of tree
struct TreeNode *newNode(int data)
{
// Create dynamic node
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
//Set data and pointer values
node->data = data;
node->left = NULL;
node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return node;
}
// Print tree elements
void preorder(struct TreeNode *node)
{
if (node != NULL)
{
//Print node value
printf(" %d", node->data);
preorder(node->left);
preorder(node->right);
}
}
// Finding the deepest left Leaf
void deepestLeftLeaf(struct TreeNode *node, int level, int *height, struct TreeNode **result)
{
if (node == NULL)
{
return;
}
// Reversibly, visit left and right subtree
deepestLeftLeaf(node->left, level + 1, height, result);
deepestLeftLeaf(node->right, level + 1, height, result);
if (node->left != NULL && node->left->left == NULL && node->left->right == NULL && level > *height)
{
// When getting new leaf deep leaf node
*height = level;
// Get node
*result = node->left;
}
}
// Handles the requests of finding a left deep leaf node
void findDeepestLLeaf(struct TreeNode *root)
{
if (root == NULL)
{
printf("\n Empty Tree\n");
return;
}
struct TreeNode *result = NULL;
int height = -1;
deepestLeftLeaf(root, 0, & height, & result);
// Display tree elements
printf("\n Tree Node : ");
preorder(root);
printf("\n Deepest left leaf Node is :");
if (result != NULL)
{
// Display deepest node
printf(" %d \n", result->data);
}
else
{
// When the leaf node is not present
printf(" None \n");
}
}
int main()
{
// Define tree
struct BinaryTree *tree1 = newTree();
struct BinaryTree *tree2 = newTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \
7 5 9
\
11
-----------------------
First Binary Tree
-----------------------
*/
tree1->root = newNode(1);
tree1->root->left = newNode(2);
tree1->root->right = newNode(8);
tree1->root->left->left = newNode(3);
tree1->root->left->right = newNode(10);
tree1->root->left->right->left = newNode(7);
tree1->root->left->right->left->right = newNode(11);
tree1->root->right->left = newNode(6);
tree1->root->right->left->right = newNode(9);
tree1->root->right->right = newNode(4);
tree1->root->right->left->left = newNode(5);
findDeepestLLeaf(tree1->root);
/*
1
/ \
/ \
2 8
\ / \
10 6 4
/ \
7 9
\
11
-----------------------
Second Binary Tree
-----------------------
*/
tree2->root = newNode(1);
tree2->root->left = newNode(2);
tree2->root->right = newNode(8);
tree2->root->left->right = newNode(10);
tree2->root->left->right->left = newNode(7);
tree2->root->left->right->left->right = newNode(11);
tree2->root->right->left = newNode(6);
tree2->root->right->left->right = newNode(9);
tree2->root->right->right = newNode(4);
findDeepestLLeaf(tree2->root);
return 0;
}
Output
Tree Node : 1 2 3 10 7 11 8 6 5 9 4
Deepest left leaf Node is : 5
Tree Node : 1 2 10 7 11 8 6 9 4
Deepest left leaf Node is : None
/*
Java Program
Deepest left leaf node in a binary tree
*/
// Tree Node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public TreeNode result;
public int height;
public BinaryTree()
{
this.root = null;
this.height = -1;
this.result = null;
}
// Print tree elements
public void preorder(TreeNode node)
{
if (node != null)
{
//Print node value
System.out.print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
// Finding the deepest left Leaf
public void deepestLeftLeaf(TreeNode node, int level)
{
if (node == null)
{
return;
}
// Reversibly, visit left and right subtree
deepestLeftLeaf(node.left, level + 1);
deepestLeftLeaf(node.right, level + 1);
if (node.left != null && node.left.left == null
&& node.left.right == null && level > height)
{
// When getting new leaf deep leaf node
this.height = level;
// Get node
this.result = node.left;
}
}
// Handles the requests of finding a left deep leaf node
public void findDeepestLLeaf()
{
if (root == null)
{
System.out.print("\n Empty Tree\n");
return;
}
this.result = null;
this.height = -1;
deepestLeftLeaf(this.root, 0);
// Display tree elements
System.out.print("\n Tree Node : ");
preorder(this.root);
System.out.print("\n Deepest left leaf Node is :");
if (this.result != null)
{
// Display deepest node
System.out.print(" " + this.result.data + " \n");
}
else
{
// When the leaf node is not present
System.out.print(" None \n");
}
}
public static void main(String[] args)
{
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \
7 5 9
\
11
-----------------------
First Binary Tree
-----------------------
*/
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(8);
tree1.root.left.left = new TreeNode(3);
tree1.root.left.right = new TreeNode(10);
tree1.root.left.right.left = new TreeNode(7);
tree1.root.left.right.left.right = new TreeNode(11);
tree1.root.right.left = new TreeNode(6);
tree1.root.right.left.right = new TreeNode(9);
tree1.root.right.right = new TreeNode(4);
tree1.root.right.left.left = new TreeNode(5);
tree1.findDeepestLLeaf();
/*
1
/ \
/ \
2 8
\ / \
10 6 4
/ \
7 9
\
11
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = new TreeNode(1);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(8);
tree2.root.left.right = new TreeNode(10);
tree2.root.left.right.left = new TreeNode(7);
tree2.root.left.right.left.right = new TreeNode(11);
tree2.root.right.left = new TreeNode(6);
tree2.root.right.left.right = new TreeNode(9);
tree2.root.right.right = new TreeNode(4);
tree2.findDeepestLLeaf();
}
}
Output
Tree Node : 1 2 3 10 7 11 8 6 5 9 4
Deepest left leaf Node is : 5
Tree Node : 1 2 10 7 11 8 6 9 4
Deepest left leaf Node is : None
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Deepest left leaf node in a binary tree
*/
// Tree Node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: TreeNode *root;
TreeNode *result;
int height;
BinaryTree()
{
this->root = NULL;
this->height = -1;
this->result = NULL;
}
// Print tree elements
void preorder(TreeNode *node)
{
if (node != NULL)
{
//Print node value
cout << " " << node->data;
this->preorder(node->left);
this->preorder(node->right);
}
}
// Finding the deepest left Leaf
void deepestLeftLeaf(TreeNode *node, int level)
{
if (node == NULL)
{
return;
}
// Reversibly, visit left and right subtree
this->deepestLeftLeaf(node->left, level + 1);
this->deepestLeftLeaf(node->right, level + 1);
if (node->left != NULL && node->left->left == NULL
&& node->left->right == NULL && level > this->height)
{
// When getting new leaf deep leaf node
this->height = level;
// Get node
this->result = node->left;
}
}
// Handles the requests of finding a left deep leaf node
void findDeepestLLeaf()
{
if (this->root == NULL)
{
cout << "\n Empty Tree\n";
return;
}
this->result = NULL;
this->height = -1;
this->deepestLeftLeaf(this->root, 0);
// Display tree elements
cout << "\n Tree Node : ";
this->preorder(this->root);
cout << "\n Deepest left leaf Node is :";
if (this->result != NULL)
{
// Display deepest node
cout << " " << this->result->data << " \n";
}
else
{
// When the leaf node is not present
cout << " None \n";
}
}
};
int main()
{
BinaryTree tree1 = BinaryTree();
BinaryTree tree2 = BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \
7 5 9
\
11
-----------------------
First Binary Tree
-----------------------
*/
tree1.root = new TreeNode(1);
tree1.root->left = new TreeNode(2);
tree1.root->right = new TreeNode(8);
tree1.root->left->left = new TreeNode(3);
tree1.root->left->right = new TreeNode(10);
tree1.root->left->right->left = new TreeNode(7);
tree1.root->left->right->left->right = new TreeNode(11);
tree1.root->right->left = new TreeNode(6);
tree1.root->right->left->right = new TreeNode(9);
tree1.root->right->right = new TreeNode(4);
tree1.root->right->left->left = new TreeNode(5);
tree1.findDeepestLLeaf();
/*
1
/ \
/ \
2 8
\ / \
10 6 4
/ \
7 9
\
11
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = new TreeNode(1);
tree2.root->left = new TreeNode(2);
tree2.root->right = new TreeNode(8);
tree2.root->left->right = new TreeNode(10);
tree2.root->left->right->left = new TreeNode(7);
tree2.root->left->right->left->right = new TreeNode(11);
tree2.root->right->left = new TreeNode(6);
tree2.root->right->left->right = new TreeNode(9);
tree2.root->right->right = new TreeNode(4);
tree2.findDeepestLLeaf();
return 0;
}
Output
Tree Node : 1 2 3 10 7 11 8 6 5 9 4
Deepest left leaf Node is : 5
Tree Node : 1 2 10 7 11 8 6 9 4
Deepest left leaf Node is : None
// Include namespace system
using System;
/*
C# Program
Deepest left leaf node in a binary tree
*/
// Tree Node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public TreeNode result;
public int height;
public BinaryTree()
{
this.root = null;
this.height = -1;
this.result = null;
}
// Print tree elements
public void preorder(TreeNode node)
{
if (node != null)
{
//Print node value
Console.Write(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
// Finding the deepest left Leaf
public void deepestLeftLeaf(TreeNode node, int level)
{
if (node == null)
{
return;
}
// Reversibly, visit left and right subtree
deepestLeftLeaf(node.left, level + 1);
deepestLeftLeaf(node.right, level + 1);
if (node.left != null && node.left.left == null && node.left.right == null && level > height)
{
// When getting new leaf deep leaf node
this.height = level;
// Get node
this.result = node.left;
}
}
// Handles the requests of finding a left deep leaf node
public void findDeepestLLeaf()
{
if (root == null)
{
Console.Write("\n Empty Tree\n");
return;
}
this.result = null;
this.height = -1;
deepestLeftLeaf(this.root, 0);
// Display tree elements
Console.Write("\n Tree Node : ");
preorder(this.root);
Console.Write("\n Deepest left leaf Node is :");
if (this.result != null)
{
// Display deepest node
Console.Write(" " + this.result.data + " \n");
}
else
{
// When the leaf node is not present
Console.Write(" None \n");
}
}
public static void Main(String[] args)
{
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \
7 5 9
\
11
-----------------------
First Binary Tree
-----------------------
*/
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(8);
tree1.root.left.left = new TreeNode(3);
tree1.root.left.right = new TreeNode(10);
tree1.root.left.right.left = new TreeNode(7);
tree1.root.left.right.left.right = new TreeNode(11);
tree1.root.right.left = new TreeNode(6);
tree1.root.right.left.right = new TreeNode(9);
tree1.root.right.right = new TreeNode(4);
tree1.root.right.left.left = new TreeNode(5);
tree1.findDeepestLLeaf();
/*
1
/ \
/ \
2 8
\ / \
10 6 4
/ \
7 9
\
11
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = new TreeNode(1);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(8);
tree2.root.left.right = new TreeNode(10);
tree2.root.left.right.left = new TreeNode(7);
tree2.root.left.right.left.right = new TreeNode(11);
tree2.root.right.left = new TreeNode(6);
tree2.root.right.left.right = new TreeNode(9);
tree2.root.right.right = new TreeNode(4);
tree2.findDeepestLLeaf();
}
}
Output
Tree Node : 1 2 3 10 7 11 8 6 5 9 4
Deepest left leaf Node is : 5
Tree Node : 1 2 10 7 11 8 6 9 4
Deepest left leaf Node is : None
<?php
/*
Php Program
Deepest left leaf node in a binary tree
*/
// Tree Node
class TreeNode
{
public $data;
public $left;
public $right;
function __construct($data)
{
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
class BinaryTree
{
public $root;
public $result;
public $height;
function __construct()
{
$this->root = null;
$this->height = -1;
$this->result = null;
}
// Print tree elements
public function preorder($node)
{
if ($node != null)
{
//Print node value
echo " ". $node->data;
$this->preorder($node->left);
$this->preorder($node->right);
}
}
// Finding the deepest left Leaf
public function deepestLeftLeaf($node, $level)
{
if ($node == null)
{
return;
}
// Reversibly, visit left and right subtree
$this->deepestLeftLeaf($node->left, $level + 1);
$this->deepestLeftLeaf($node->right, $level + 1);
if ($node->left != null && $node->left->left == null
&& $node->left->right == null && $level > $this->height)
{
// When getting new leaf deep leaf node
$this->height = $level;
// Get node
$this->result = $node->left;
}
}
// Handles the requests of finding a left deep leaf node
public function findDeepestLLeaf()
{
if ($this->root == null)
{
echo "\n Empty Tree\n";
return;
}
$this->result = null;
$this->height = -1;
$this->deepestLeftLeaf($this->root, 0);
// Display tree elements
echo "\n Tree Node : ";
$this->preorder($this->root);
echo "\n Deepest left leaf Node is :";
if ($this->result != null)
{
// Display deepest node
echo " ". $this->result->data ." \n";
}
else
{
// When the leaf node is not present
echo " None \n";
}
}
}
function main()
{
$tree1 = new BinaryTree();
$tree2 = new BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \
7 5 9
\
11
-----------------------
First Binary Tree
-----------------------
*/
$tree1->root = new TreeNode(1);
$tree1->root->left = new TreeNode(2);
$tree1->root->right = new TreeNode(8);
$tree1->root->left->left = new TreeNode(3);
$tree1->root->left->right = new TreeNode(10);
$tree1->root->left->right->left = new TreeNode(7);
$tree1->root->left->right->left->right = new TreeNode(11);
$tree1->root->right->left = new TreeNode(6);
$tree1->root->right->left->right = new TreeNode(9);
$tree1->root->right->right = new TreeNode(4);
$tree1->root->right->left->left = new TreeNode(5);
$tree1->findDeepestLLeaf();
/*
1
/ \
/ \
2 8
\ / \
10 6 4
/ \
7 9
\
11
-----------------------
Second Binary Tree
-----------------------
*/
$tree2->root = new TreeNode(1);
$tree2->root->left = new TreeNode(2);
$tree2->root->right = new TreeNode(8);
$tree2->root->left->right = new TreeNode(10);
$tree2->root->left->right->left = new TreeNode(7);
$tree2->root->left->right->left->right = new TreeNode(11);
$tree2->root->right->left = new TreeNode(6);
$tree2->root->right->left->right = new TreeNode(9);
$tree2->root->right->right = new TreeNode(4);
$tree2->findDeepestLLeaf();
}
main();
Output
Tree Node : 1 2 3 10 7 11 8 6 5 9 4
Deepest left leaf Node is : 5
Tree Node : 1 2 10 7 11 8 6 9 4
Deepest left leaf Node is : None
/*
Node Js Program
Deepest left leaf node in a binary tree
*/
// Tree Node
class TreeNode
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
this.height = -1;
this.result = null;
}
// Print tree elements
preorder(node)
{
if (node != null)
{
//Print node value
process.stdout.write(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
// Finding the deepest left Leaf
deepestLeftLeaf(node, level)
{
if (node == null)
{
return;
}
// Reversibly, visit left and right subtree
this.deepestLeftLeaf(node.left, level + 1);
this.deepestLeftLeaf(node.right, level + 1);
if (node.left != null && node.left.left == null && node.left.right == null && level > this.height)
{
// When getting new leaf deep leaf node
this.height = level;
// Get node
this.result = node.left;
}
}
// Handles the requests of finding a left deep leaf node
findDeepestLLeaf()
{
if (this.root == null)
{
process.stdout.write("\n Empty Tree\n");
return;
}
this.result = null;
this.height = -1;
this.deepestLeftLeaf(this.root, 0);
// Display tree elements
process.stdout.write("\n Tree Node : ");
this.preorder(this.root);
process.stdout.write("\n Deepest left leaf Node is :");
if (this.result != null)
{
// Display deepest node
process.stdout.write(" " + this.result.data + " \n");
}
else
{
// When the leaf node is not present
process.stdout.write(" None \n");
}
}
}
function main()
{
var tree1 = new BinaryTree();
var tree2 = new BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \
7 5 9
\
11
-----------------------
First Binary Tree
-----------------------
*/
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(8);
tree1.root.left.left = new TreeNode(3);
tree1.root.left.right = new TreeNode(10);
tree1.root.left.right.left = new TreeNode(7);
tree1.root.left.right.left.right = new TreeNode(11);
tree1.root.right.left = new TreeNode(6);
tree1.root.right.left.right = new TreeNode(9);
tree1.root.right.right = new TreeNode(4);
tree1.root.right.left.left = new TreeNode(5);
tree1.findDeepestLLeaf();
/*
1
/ \
/ \
2 8
\ / \
10 6 4
/ \
7 9
\
11
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = new TreeNode(1);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(8);
tree2.root.left.right = new TreeNode(10);
tree2.root.left.right.left = new TreeNode(7);
tree2.root.left.right.left.right = new TreeNode(11);
tree2.root.right.left = new TreeNode(6);
tree2.root.right.left.right = new TreeNode(9);
tree2.root.right.right = new TreeNode(4);
tree2.findDeepestLLeaf();
}
main();
Output
Tree Node : 1 2 3 10 7 11 8 6 5 9 4
Deepest left leaf Node is : 5
Tree Node : 1 2 10 7 11 8 6 9 4
Deepest left leaf Node is : None
# Python 3 Program
# Deepest left leaf node in a binary tree
# Tree Node
class TreeNode :
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
self.height = -1
self.result = None
# Print tree elements
def preorder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
self.preorder(node.left)
self.preorder(node.right)
# Finding the deepest left Leaf
def deepestLeftLeaf(self, node, level) :
if (node == None) :
return
# Reversibly, visit left and right subtree
self.deepestLeftLeaf(node.left, level + 1)
self.deepestLeftLeaf(node.right, level + 1)
if (node.left != None and node.left.left == None and node.left.right == None and level > self.height) :
# When getting new leaf deep leaf node
self.height = level
# Get node
self.result = node.left
# Handles the requests of finding a left deep leaf node
def findDeepestLLeaf(self) :
if (self.root == None) :
print("\n Empty Tree")
return
self.result = None
self.height = -1
self.deepestLeftLeaf(self.root, 0)
# Display tree elements
print("\n Tree Node :", end = "")
self.preorder(self.root)
print("\n Deepest left leaf Node is :", end = "")
if (self.result != None) :
# Display deepest node
print(" ", self.result.data ," ")
else :
# When the leaf node is not present
print(" None ")
def main() :
tree1 = BinaryTree()
tree2 = BinaryTree()
#
# 1
# / \
# / \
# 2 8
# / \ / \
# 3 10 6 4
# / / \
# 7 5 9
# \
# 11
# -----------------------
# First Binary Tree
# -----------------------
tree1.root = TreeNode(1)
tree1.root.left = TreeNode(2)
tree1.root.right = TreeNode(8)
tree1.root.left.left = TreeNode(3)
tree1.root.left.right = TreeNode(10)
tree1.root.left.right.left = TreeNode(7)
tree1.root.left.right.left.right = TreeNode(11)
tree1.root.right.left = TreeNode(6)
tree1.root.right.left.right = TreeNode(9)
tree1.root.right.right = TreeNode(4)
tree1.root.right.left.left = TreeNode(5)
tree1.findDeepestLLeaf()
#
# 1
# / \
# / \
# 2 8
# \ / \
# 10 6 4
# / \
# 7 9
# \
# 11
# -----------------------
# Second Binary Tree
# -----------------------
tree2.root = TreeNode(1)
tree2.root.left = TreeNode(2)
tree2.root.right = TreeNode(8)
tree2.root.left.right = TreeNode(10)
tree2.root.left.right.left = TreeNode(7)
tree2.root.left.right.left.right = TreeNode(11)
tree2.root.right.left = TreeNode(6)
tree2.root.right.left.right = TreeNode(9)
tree2.root.right.right = TreeNode(4)
tree2.findDeepestLLeaf()
if __name__ == "__main__": main()
Output
Tree Node : 1 2 3 10 7 11 8 6 5 9 4
Deepest left leaf Node is : 5
Tree Node : 1 2 10 7 11 8 6 9 4
Deepest left leaf Node is : None
# Ruby Program
# Deepest left leaf node in a binary tree
# Tree Node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
self.data = data
self.left = nil
self.right = nil
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root, :result, :height
attr_accessor :root, :result, :height
def initialize()
self.root = nil
self.height = -1
self.result = nil
end
# Print tree elements
def preorder(node)
if (node != nil)
# Print node value
print(" ", node.data)
self.preorder(node.left)
self.preorder(node.right)
end
end
# Finding the deepest left Leaf
def deepestLeftLeaf(node, level)
if (node == nil)
return
end
# Reversibly, visit left and right subtree
self.deepestLeftLeaf(node.left, level + 1)
self.deepestLeftLeaf(node.right, level + 1)
if (node.left != nil && node.left.left == nil && node.left.right == nil && level > height)
# When getting new leaf deep leaf node
self.height = level
# Get node
self.result = node.left
end
end
# Handles the requests of finding a left deep leaf node
def findDeepestLLeaf()
if (root == nil)
print("\n Empty Tree\n")
return
end
self.result = nil
self.height = -1
self.deepestLeftLeaf(self.root, 0)
# Display tree elements
print("\n Tree Node : ")
self.preorder(self.root)
print("\n Deepest left leaf Node is :")
if (self.result != nil)
# Display deepest node
print(" ", self.result.data ," \n")
else
# When the leaf node is not present
print(" None \n")
end
end
end
def main()
tree1 = BinaryTree.new()
tree2 = BinaryTree.new()
#
# 1
# / \
# / \
# 2 8
# / \ / \
# 3 10 6 4
# / / \
# 7 5 9
# \
# 11
# -----------------------
# First Binary Tree
# -----------------------
tree1.root = TreeNode.new(1)
tree1.root.left = TreeNode.new(2)
tree1.root.right = TreeNode.new(8)
tree1.root.left.left = TreeNode.new(3)
tree1.root.left.right = TreeNode.new(10)
tree1.root.left.right.left = TreeNode.new(7)
tree1.root.left.right.left.right = TreeNode.new(11)
tree1.root.right.left = TreeNode.new(6)
tree1.root.right.left.right = TreeNode.new(9)
tree1.root.right.right = TreeNode.new(4)
tree1.root.right.left.left = TreeNode.new(5)
tree1.findDeepestLLeaf()
#
# 1
# / \
# / \
# 2 8
# \ / \
# 10 6 4
# / \
# 7 9
# \
# 11
# -----------------------
# Second Binary Tree
# -----------------------
tree2.root = TreeNode.new(1)
tree2.root.left = TreeNode.new(2)
tree2.root.right = TreeNode.new(8)
tree2.root.left.right = TreeNode.new(10)
tree2.root.left.right.left = TreeNode.new(7)
tree2.root.left.right.left.right = TreeNode.new(11)
tree2.root.right.left = TreeNode.new(6)
tree2.root.right.left.right = TreeNode.new(9)
tree2.root.right.right = TreeNode.new(4)
tree2.findDeepestLLeaf()
end
main()
Output
Tree Node : 1 2 3 10 7 11 8 6 5 9 4
Deepest left leaf Node is : 5
Tree Node : 1 2 10 7 11 8 6 9 4
Deepest left leaf Node is : None
/*
Scala Program
Deepest left leaf node in a binary tree
*/
// Tree Node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinaryTree(var root: TreeNode , var result: TreeNode , var height: Int)
{
def this()
{
this(null, null, -1);
}
// Print tree elements
def preorder(node: TreeNode): Unit = {
if (node != null)
{
//Print node value
print(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
// Finding the deepest left Leaf
def deepestLeftLeaf(node: TreeNode, level: Int): Unit = {
if (node == null)
{
return;
}
// Reversibly, visit left and right subtree
this.deepestLeftLeaf(node.left, level + 1);
this.deepestLeftLeaf(node.right, level + 1);
if (node.left != null && node.left.left == null && node.left.right == null && level > height)
{
// When getting new leaf deep leaf node
this.height = level;
// Get node
this.result = node.left;
}
}
// Handles the requests of finding a left deep leaf node
def findDeepestLLeaf(): Unit = {
if (root == null)
{
print("\n Empty Tree\n");
return;
}
this.result = null;
this.height = -1;
this.deepestLeftLeaf(this.root, 0);
// Display tree elements
print("\n Tree Node : ");
this.preorder(this.root);
print("\n Deepest left leaf Node is :");
if (this.result != null)
{
// Display deepest node
print(" " + this.result.data + " \n");
}
else
{
// When the leaf node is not present
print(" None \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree1: BinaryTree = new BinaryTree();
var tree2: BinaryTree = new BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \
7 5 9
\
11
-----------------------
First Binary Tree
-----------------------
*/
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(8);
tree1.root.left.left = new TreeNode(3);
tree1.root.left.right = new TreeNode(10);
tree1.root.left.right.left = new TreeNode(7);
tree1.root.left.right.left.right = new TreeNode(11);
tree1.root.right.left = new TreeNode(6);
tree1.root.right.left.right = new TreeNode(9);
tree1.root.right.right = new TreeNode(4);
tree1.root.right.left.left = new TreeNode(5);
tree1.findDeepestLLeaf();
/*
1
/ \
/ \
2 8
\ / \
10 6 4
/ \
7 9
\
11
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = new TreeNode(1);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(8);
tree2.root.left.right = new TreeNode(10);
tree2.root.left.right.left = new TreeNode(7);
tree2.root.left.right.left.right = new TreeNode(11);
tree2.root.right.left = new TreeNode(6);
tree2.root.right.left.right = new TreeNode(9);
tree2.root.right.right = new TreeNode(4);
tree2.findDeepestLLeaf();
}
}
Output
Tree Node : 1 2 3 10 7 11 8 6 5 9 4
Deepest left leaf Node is : 5
Tree Node : 1 2 10 7 11 8 6 9 4
Deepest left leaf Node is : None
/*
Kotlin Program
Deepest left leaf node in a binary tree
*/
// Tree Node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
var result: TreeNode ? ;
var height: Int;
constructor()
{
this.root = null;
this.height = -1;
this.result = null;
}
// Print tree elements
fun preorder(node: TreeNode ? ): Unit
{
if (node != null)
{
//Print node value
print(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
// Finding the deepest left Leaf
fun deepestLeftLeaf(node: TreeNode ? , level : Int): Unit
{
if (node == null)
{
return;
}
// Reversibly, visit left and right subtree
this.deepestLeftLeaf(node.left, level + 1);
this.deepestLeftLeaf(node.right, level + 1);
if (node.left != null && node.left?.left == null
&& node.left?.right == null && level > height)
{
// When getting new leaf deep leaf node
this.height = level;
// Get node
this.result = node.left;
}
}
// Handles the requests of finding a left deep leaf node
fun findDeepestLLeaf(): Unit
{
if (root == null)
{
print("\n Empty Tree\n");
return;
}
this.result = null;
this.height = -1;
this.deepestLeftLeaf(this.root, 0);
// Display tree elements
print("\n Tree Node : ");
this.preorder(this.root);
print("\n Deepest left leaf Node is :");
if (this.result != null)
{
// Display deepest node
print(" " + this.result!!.data + " \n");
}
else
{
// When the leaf node is not present
print(" None \n");
}
}
}
fun main(args: Array < String > ): Unit
{
var tree1: BinaryTree = BinaryTree();
var tree2: BinaryTree = BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \
7 5 9
\
11
-----------------------
First Binary Tree
-----------------------
*/
tree1.root = TreeNode(1);
tree1.root?.left = TreeNode(2);
tree1.root?.right = TreeNode(8);
tree1.root?.left?.left = TreeNode(3);
tree1.root?.left?.right = TreeNode(10);
tree1.root?.left?.right?.left = TreeNode(7);
tree1.root?.left?.right?.left?.right = TreeNode(11);
tree1.root?.right?.left = TreeNode(6);
tree1.root?.right?.left?.right = TreeNode(9);
tree1.root?.right?.right = TreeNode(4);
tree1.root?.right?.left?.left = TreeNode(5);
tree1.findDeepestLLeaf();
/*
1
/ \
/ \
2 8
\ / \
10 6 4
/ \
7 9
\
11
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = TreeNode(1);
tree2.root?.left = TreeNode(2);
tree2.root?.right = TreeNode(8);
tree2.root?.left?.right = TreeNode(10);
tree2.root?.left?.right?.left = TreeNode(7);
tree2.root?.left?.right?.left?.right = TreeNode(11);
tree2.root?.right?.left = TreeNode(6);
tree2.root?.right?.left?.right = TreeNode(9);
tree2.root?.right?.right = TreeNode(4);
tree2.findDeepestLLeaf();
}
Output
Tree Node : 1 2 3 10 7 11 8 6 5 9 4
Deepest left leaf Node is : 5
Tree Node : 1 2 10 7 11 8 6 9 4
Deepest left leaf Node is : None
/*
Swift 4 Program
Deepest left leaf node in a binary tree
*/
// Tree Node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
var result: TreeNode? ;
var height: Int;
init()
{
self.root = nil;
self.height = -1;
self.result = nil;
}
// Print tree elements
func preorder(_ node: TreeNode? )
{
if (node != nil)
{
//Print node value
print(" ", node!.data, terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
// Finding the deepest left Leaf
func deepestLeftLeaf(_ node: TreeNode? , _ level : Int)
{
if (node == nil)
{
return;
}
// Reversibly, visit left and right subtree
self.deepestLeftLeaf(node!.left, level + 1);
self.deepestLeftLeaf(node!.right, level + 1);
if (node!.left != nil && node!.left!.left == nil && node!.left!.right == nil && level > self.height)
{
// When getting new leaf deep leaf node
self.height = level;
// Get node
self.result = node!.left;
}
}
// Handles the requests of finding a left deep leaf node
func findDeepestLLeaf()
{
if (self.root == nil)
{
print("\n Empty Tree");
return;
}
self.result = nil;
self.height = -1;
self.deepestLeftLeaf(self.root, 0);
// Display tree elements
print("\n Tree Node : ", terminator: "");
self.preorder(self.root);
print("\n Deepest left leaf Node is :", terminator: "");
if (self.result != nil)
{
// Display deepest node
print(" ", self.result!.data ," ");
}
else
{
// When the leaf node is not present
print(" None ");
}
}
}
func main()
{
let tree1: BinaryTree = BinaryTree();
let tree2: BinaryTree = BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \
7 5 9
\
11
-----------------------
First Binary Tree
-----------------------
*/
tree1.root = TreeNode(1);
tree1.root!.left = TreeNode(2);
tree1.root!.right = TreeNode(8);
tree1.root!.left!.left = TreeNode(3);
tree1.root!.left!.right = TreeNode(10);
tree1.root!.left!.right!.left = TreeNode(7);
tree1.root!.left!.right!.left!.right = TreeNode(11);
tree1.root!.right!.left = TreeNode(6);
tree1.root!.right!.left!.right = TreeNode(9);
tree1.root!.right!.right = TreeNode(4);
tree1.root!.right!.left!.left = TreeNode(5);
tree1.findDeepestLLeaf();
/*
1
/ \
/ \
2 8
\ / \
10 6 4
/ \
7 9
\
11
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = TreeNode(1);
tree2.root!.left = TreeNode(2);
tree2.root!.right = TreeNode(8);
tree2.root!.left!.right = TreeNode(10);
tree2.root!.left!.right!.left = TreeNode(7);
tree2.root!.left!.right!.left!.right = TreeNode(11);
tree2.root!.right!.left = TreeNode(6);
tree2.root!.right!.left!.right = TreeNode(9);
tree2.root!.right!.right = TreeNode(4);
tree2.findDeepestLLeaf();
}
main();
Output
Tree Node : 1 2 3 10 7 11 8 6 5 9 4
Deepest left leaf Node is : 5
Tree Node : 1 2 10 7 11 8 6 9 4
Deepest left leaf Node is : None
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment