Find the deepest node in binary tree

Here given code implementation process.
/*
C Program
Deepest node in 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);
}
}
// Find deepest node in binary tree
void findDeepest(struct TreeNode *node, int level, int *height, int *result)
{
if (node == NULL)
{
return;
}
// Reversibly, visit left and right subtree
findDeepest(node->left, level + 1, height, result);
findDeepest(node->right, level + 1, height, result);
if (level > *height)
{
// When get a new higher level
*height = level;
// Get node data
*result = node->data;
}
}
// Handles the request of find the deepest node in a binary tree
void findDeepestNode(struct TreeNode *root)
{
if (root == NULL)
{
printf("\n Empty Tree\n");
return;
}
int result = 0;
int height = -1;
findDeepest(root, 0, & height, & result);
// Display tree elements
printf("\n Tree Node : ");
preorder(root);
// Display deepest node
printf("\n Deepest Node is : %d \n", result);
}
int main()
{
// Define tree
struct BinaryTree *tree1 = newTree();
struct BinaryTree *tree2 = newTree();
/*
1
/ \
2 8
/ \ /
3 10 6
/
7
-----------------------
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->right->left = newNode(6);
findDeepestNode(tree1->root);
/*
1
/ \
2 8
/ \ / \
3 10 6 9
/ \
5 4
-----------------------
Second Binary Tree
-----------------------
*/
tree2->root = newNode(1);
tree2->root->left = newNode(2);
tree2->root->right = newNode(8);
tree2->root->left->left = newNode(3);
tree2->root->left->right = newNode(10);
tree2->root->right->left = newNode(6);
tree2->root->right->left->left = newNode(5);
tree2->root->right->right = newNode(9);
tree2->root->right->right->right = newNode(4);
// When more than one node exist in deepest level
// In above tree (5,4), Then pick first node
findDeepestNode(tree2->root);
return 0;
}
Output
Tree Node : 1 2 3 10 7 8 6
Deepest Node is : 7
Tree Node : 1 2 3 10 8 6 5 9 4
Deepest Node is : 5
/*
Java Program
Find the deepest node in 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 int result;
public int height;
public BinaryTree()
{
this.root = null;
this.height = -1;
this.result = 0;
}
// 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);
}
}
// Find deepest node in binary tree
public void findDeepest(TreeNode node, int level)
{
if (node == null)
{
return;
}
// Reversibly, visit left and right subtree
findDeepest(node.left, level + 1);
findDeepest(node.right, level + 1);
if (level > this.height)
{
// When get a new higher level
this.height = level;
// Get node data
this.result = node.data;
}
}
// Handles the request of find the deepest node in a binary tree
public void findDeepestNode(TreeNode root)
{
if (root == null)
{
System.out.print("\n Empty Tree\n");
return;
}
this.result = 0;
this.height = -1;
findDeepest(root, 0);
// Display tree elements
System.out.print("\n Tree Node : ");
preorder(root);
// Display deepest node
System.out.print("\n Deepest Node is : " + result + " \n");
}
public static void main(String[] args)
{
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
1
/ \
2 8
/ \ /
3 10 6
/
7
-----------------------
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.right.left = new TreeNode(6);
tree2.findDeepestNode(tree1.root);
/*
1
/ \
2 8
/ \ / \
3 10 6 9
/ \
5 4
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = new TreeNode(1);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(8);
tree2.root.left.left = new TreeNode(3);
tree2.root.left.right = new TreeNode(10);
tree2.root.right.left = new TreeNode(6);
tree2.root.right.left.left = new TreeNode(5);
tree2.root.right.right = new TreeNode(9);
tree2.root.right.right.right = new TreeNode(4);
// When more than one node exist in deepest level
// In above tree (5,4), Then pick first node
tree2.findDeepestNode(tree2.root);
}
}
Output
Tree Node : 1 2 3 10 7 8 6
Deepest Node is : 7
Tree Node : 1 2 3 10 8 6 5 9 4
Deepest Node is : 5
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Find the deepest node in 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;
int result;
int height;
BinaryTree()
{
this->root = NULL;
this->height = -1;
this->result = 0;
}
// Print tree elements
void preorder(TreeNode *node)
{
if (node != NULL)
{
//Print node value
cout << " " << node->data;
this->preorder(node->left);
this->preorder(node->right);
}
}
// Find deepest node in binary tree
void findDeepest(TreeNode *node, int level)
{
if (node == NULL)
{
return;
}
// Reversibly, visit left and right subtree
this->findDeepest(node->left, level + 1);
this->findDeepest(node->right, level + 1);
if (level > this->height)
{
// When get a new higher level
this->height = level;
// Get node data
this->result = node->data;
}
}
// Handles the request of find the deepest node in a binary tree
void findDeepestNode(TreeNode *root)
{
if (root == NULL)
{
cout << "\n Empty Tree\n";
return;
}
this->result = 0;
this->height = -1;
this->findDeepest(root, 0);
// Display tree elements
cout << "\n Tree Node : ";
this->preorder(root);
// Display deepest node
cout << "\n Deepest Node is : " << this->result << " \n";
}
};
int main()
{
BinaryTree *tree1 = new BinaryTree();
BinaryTree tree2 = BinaryTree();
/*
1
/ \
2 8
/ \ /
3 10 6
/
7
-----------------------
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->right->left = new TreeNode(6);
tree2.findDeepestNode(tree1->root);
/*
1
/ \
2 8
/ \ / \
3 10 6 9
/ \
5 4
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = new TreeNode(1);
tree2.root->left = new TreeNode(2);
tree2.root->right = new TreeNode(8);
tree2.root->left->left = new TreeNode(3);
tree2.root->left->right = new TreeNode(10);
tree2.root->right->left = new TreeNode(6);
tree2.root->right->left->left = new TreeNode(5);
tree2.root->right->right = new TreeNode(9);
tree2.root->right->right->right = new TreeNode(4);
// When more than one node exist in deepest level
// In above tree (5,4), Then pick first node
tree2.findDeepestNode(tree2.root);
return 0;
}
Output
Tree Node : 1 2 3 10 7 8 6
Deepest Node is : 7
Tree Node : 1 2 3 10 8 6 5 9 4
Deepest Node is : 5
// Include namespace system
using System;
/*
C# Program
Find the deepest node in 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 int result;
public int height;
public BinaryTree()
{
this.root = null;
this.height = -1;
this.result = 0;
}
// Print tree elements
public void preorder(TreeNode node)
{
if (node != null)
{
//Print node value
Console.Write(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
// Find deepest node in binary tree
public void findDeepest(TreeNode node, int level)
{
if (node == null)
{
return;
}
// Reversibly, visit left and right subtree
findDeepest(node.left, level + 1);
findDeepest(node.right, level + 1);
if (level > this.height)
{
// When get a new higher level
this.height = level;
// Get node data
this.result = node.data;
}
}
// Handles the request of find the deepest node in a binary tree
public void findDeepestNode(TreeNode root)
{
if (root == null)
{
Console.Write("\n Empty Tree\n");
return;
}
this.result = 0;
this.height = -1;
findDeepest(root, 0);
// Display tree elements
Console.Write("\n Tree Node : ");
preorder(root);
// Display deepest node
Console.Write("\n Deepest Node is : " + result + " \n");
}
public static void Main(String[] args)
{
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
1
/ \
2 8
/ \ /
3 10 6
/
7
-----------------------
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.right.left = new TreeNode(6);
tree2.findDeepestNode(tree1.root);
/*
1
/ \
2 8
/ \ / \
3 10 6 9
/ \
5 4
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = new TreeNode(1);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(8);
tree2.root.left.left = new TreeNode(3);
tree2.root.left.right = new TreeNode(10);
tree2.root.right.left = new TreeNode(6);
tree2.root.right.left.left = new TreeNode(5);
tree2.root.right.right = new TreeNode(9);
tree2.root.right.right.right = new TreeNode(4);
// When more than one node exist in deepest level
// In above tree (5,4), Then pick first node
tree2.findDeepestNode(tree2.root);
}
}
Output
Tree Node : 1 2 3 10 7 8 6
Deepest Node is : 7
Tree Node : 1 2 3 10 8 6 5 9 4
Deepest Node is : 5
<?php
/*
Php Program
Find the deepest node in 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 = 0;
}
// Print tree elements
public function preorder($node)
{
if ($node != null)
{
//Print node value
echo " ". $node->data;
$this->preorder($node->left);
$this->preorder($node->right);
}
}
// Find deepest node in binary tree
public function findDeepest($node, $level)
{
if ($node == null)
{
return;
}
// Reversibly, visit left and right subtree
$this->findDeepest($node->left, $level + 1);
$this->findDeepest($node->right, $level + 1);
if ($level > $this->height)
{
// When get a new higher level
$this->height = $level;
// Get node data
$this->result = $node->data;
}
}
// Handles the request of find the deepest node in a binary tree
public function findDeepestNode($root)
{
if ($root == null)
{
echo "\n Empty Tree\n";
return;
}
$this->result = 0;
$this->height = -1;
$this->findDeepest($root, 0);
// Display tree elements
echo "\n Tree Node : ";
$this->preorder($root);
// Display deepest node
echo "\n Deepest Node is : ". $this->result ." \n";
}
}
function main()
{
$tree1 = new BinaryTree();
$tree2 = new BinaryTree();
/*
1
/ \
2 8
/ \ /
3 10 6
/
7
-----------------------
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->right->left = new TreeNode(6);
$tree2->findDeepestNode($tree1->root);
/*
1
/ \
2 8
/ \ / \
3 10 6 9
/ \
5 4
-----------------------
Second Binary Tree
-----------------------
*/
$tree2->root = new TreeNode(1);
$tree2->root->left = new TreeNode(2);
$tree2->root->right = new TreeNode(8);
$tree2->root->left->left = new TreeNode(3);
$tree2->root->left->right = new TreeNode(10);
$tree2->root->right->left = new TreeNode(6);
$tree2->root->right->left->left = new TreeNode(5);
$tree2->root->right->right = new TreeNode(9);
$tree2->root->right->right->right = new TreeNode(4);
// When more than one node exist in deepest level
// In above tree (5,4), Then pick first node
$tree2->findDeepestNode($tree2->root);
}
main();
Output
Tree Node : 1 2 3 10 7 8 6
Deepest Node is : 7
Tree Node : 1 2 3 10 8 6 5 9 4
Deepest Node is : 5
/*
Node Js Program
Find the deepest node in 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 = 0;
}
// Print tree elements
preorder(node)
{
if (node != null)
{
//Print node value
process.stdout.write(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
// Find deepest node in binary tree
findDeepest(node, level)
{
if (node == null)
{
return;
}
// Reversibly, visit left and right subtree
this.findDeepest(node.left, level + 1);
this.findDeepest(node.right, level + 1);
if (level > this.height)
{
// When get a new higher level
this.height = level;
// Get node data
this.result = node.data;
}
}
// Handles the request of find the deepest node in a binary tree
findDeepestNode(root)
{
if (root == null)
{
process.stdout.write("\n Empty Tree\n");
return;
}
this.result = 0;
this.height = -1;
this.findDeepest(root, 0);
// Display tree elements
process.stdout.write("\n Tree Node : ");
this.preorder(root);
// Display deepest node
process.stdout.write("\n Deepest Node is : " + this.result + " \n");
}
}
function main()
{
var tree1 = new BinaryTree();
var tree2 = new BinaryTree();
/*
1
/ \
2 8
/ \ /
3 10 6
/
7
-----------------------
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.right.left = new TreeNode(6);
tree2.findDeepestNode(tree1.root);
/*
1
/ \
2 8
/ \ / \
3 10 6 9
/ \
5 4
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = new TreeNode(1);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(8);
tree2.root.left.left = new TreeNode(3);
tree2.root.left.right = new TreeNode(10);
tree2.root.right.left = new TreeNode(6);
tree2.root.right.left.left = new TreeNode(5);
tree2.root.right.right = new TreeNode(9);
tree2.root.right.right.right = new TreeNode(4);
// When more than one node exist in deepest level
// In above tree (5,4), Then pick first node
tree2.findDeepestNode(tree2.root);
}
main();
Output
Tree Node : 1 2 3 10 7 8 6
Deepest Node is : 7
Tree Node : 1 2 3 10 8 6 5 9 4
Deepest Node is : 5
# Python 3 Program
# Find the deepest node in 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 = 0
# 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)
# Find deepest node in binary tree
def findDeepest(self, node, level) :
if (node == None) :
return
# Reversibly, visit left and right subtree
self.findDeepest(node.left, level + 1)
self.findDeepest(node.right, level + 1)
if (level > self.height) :
# When get a new higher level
self.height = level
# Get node data
self.result = node.data
# Handles the request of find the deepest node in a binary tree
def findDeepestNode(self, root) :
if (root == None) :
print("\n Empty Tree")
return
self.result = 0
self.height = -1
self.findDeepest(root, 0)
# Display tree elements
print("\n Tree Node : ", end = "")
self.preorder(root)
# Display deepest node
print("\n Deepest Node is : ", self.result ," ")
def main() :
tree1 = BinaryTree()
tree2 = BinaryTree()
#
# 1
# / \
# 2 8
# / \ /
# 3 10 6
# /
# 7
# -----------------------
# 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.right.left = TreeNode(6)
tree2.findDeepestNode(tree1.root)
#
# 1
# / \
# 2 8
# / \ / \
# 3 10 6 9
# / \
# 5 4
# -----------------------
# Second Binary Tree
# -----------------------
#
tree2.root = TreeNode(1)
tree2.root.left = TreeNode(2)
tree2.root.right = TreeNode(8)
tree2.root.left.left = TreeNode(3)
tree2.root.left.right = TreeNode(10)
tree2.root.right.left = TreeNode(6)
tree2.root.right.left.left = TreeNode(5)
tree2.root.right.right = TreeNode(9)
tree2.root.right.right.right = TreeNode(4)
# When more than one node exist in deepest level
# In above tree (5,4), Then pick first node
tree2.findDeepestNode(tree2.root)
if __name__ == "__main__": main()
Output
Tree Node : 1 2 3 10 7 8 6
Deepest Node is : 7
Tree Node : 1 2 3 10 8 6 5 9 4
Deepest Node is : 5
# Ruby Program
# Find the deepest node in 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 = 0
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
# Find deepest node in binary tree
def findDeepest(node, level)
if (node == nil)
return
end
# Reversibly, visit left and right subtree
self.findDeepest(node.left, level + 1)
self.findDeepest(node.right, level + 1)
if (level > self.height)
# When get a new higher level
self.height = level
# Get node data
self.result = node.data
end
end
# Handles the request of find the deepest node in a binary tree
def findDeepestNode(root)
if (root == nil)
print("\n Empty Tree\n")
return
end
self.result = 0
self.height = -1
self.findDeepest(root, 0)
# Display tree elements
print("\n Tree Node : ")
self.preorder(root)
# Display deepest node
print("\n Deepest Node is : ", result ," \n")
end
end
def main()
tree1 = BinaryTree.new()
tree2 = BinaryTree.new()
#
# 1
# / \
# 2 8
# / \ /
# 3 10 6
# /
# 7
# -----------------------
# 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.right.left = TreeNode.new(6)
tree2.findDeepestNode(tree1.root)
#
# 1
# / \
# 2 8
# / \ / \
# 3 10 6 9
# / \
# 5 4
# -----------------------
# Second Binary Tree
# -----------------------
#
tree2.root = TreeNode.new(1)
tree2.root.left = TreeNode.new(2)
tree2.root.right = TreeNode.new(8)
tree2.root.left.left = TreeNode.new(3)
tree2.root.left.right = TreeNode.new(10)
tree2.root.right.left = TreeNode.new(6)
tree2.root.right.left.left = TreeNode.new(5)
tree2.root.right.right = TreeNode.new(9)
tree2.root.right.right.right = TreeNode.new(4)
# When more than one node exist in deepest level
# In above tree (5,4), Then pick first node
tree2.findDeepestNode(tree2.root)
end
main()
Output
Tree Node : 1 2 3 10 7 8 6
Deepest Node is : 7
Tree Node : 1 2 3 10 8 6 5 9 4
Deepest Node is : 5
/*
Scala Program
Find the deepest node in 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: Int , var height: Int)
{
def this()
{
this(null, 0, -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);
}
}
// Find deepest node in binary tree
def findDeepest(node: TreeNode, level: Int): Unit = {
if (node == null)
{
return;
}
// Reversibly, visit left and right subtree
this.findDeepest(node.left, level + 1);
this.findDeepest(node.right, level + 1);
if (level > this.height)
{
// When get a new higher level
this.height = level;
// Get node data
this.result = node.data;
}
}
// Handles the request of find the deepest node in a binary tree
def findDeepestNode(root: TreeNode): Unit = {
if (root == null)
{
print("\n Empty Tree\n");
return;
}
this.result = 0;
this.height = -1;
this.findDeepest(root, 0);
// Display tree elements
print("\n Tree Node : ");
this.preorder(root);
// Display deepest node
print("\n Deepest Node is : " + result + " \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
/
7
-----------------------
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.right.left = new TreeNode(6);
tree2.findDeepestNode(tree1.root);
/*
1
/ \
2 8
/ \ / \
3 10 6 9
/ \
5 4
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = new TreeNode(1);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(8);
tree2.root.left.left = new TreeNode(3);
tree2.root.left.right = new TreeNode(10);
tree2.root.right.left = new TreeNode(6);
tree2.root.right.left.left = new TreeNode(5);
tree2.root.right.right = new TreeNode(9);
tree2.root.right.right.right = new TreeNode(4);
// When more than one node exist in deepest level
// In above tree (5,4), Then pick first node
tree2.findDeepestNode(tree2.root);
}
}
Output
Tree Node : 1 2 3 10 7 8 6
Deepest Node is : 7
Tree Node : 1 2 3 10 8 6 5 9 4
Deepest Node is : 5
/*
Swift 4 Program
Find the deepest node in 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: Int;
var height: Int;
init()
{
self.root = nil;
self.height = -1;
self.result = 0;
}
// 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);
}
}
// Find deepest node in binary tree
func findDeepest(_ node: TreeNode? , _ level : Int)
{
if (node == nil)
{
return;
}
// Reversibly, visit left and right subtree
self.findDeepest(node!.left, level + 1);
self.findDeepest(node!.right, level + 1);
if (level > self.height)
{
// When get a new higher level
self.height = level;
// Get node data
self.result = node!.data;
}
}
// Handles the request of find the deepest node in a binary tree
func findDeepestNode(_ root: TreeNode? )
{
if (root == nil)
{
print("\n Empty Tree");
return;
}
self.result = 0;
self.height = -1;
self.findDeepest(root, 0);
// Display tree elements
print("\n Tree Node : ", terminator: "");
self.preorder(root);
// Display deepest node
print("\n Deepest Node is : ", self.result ," ");
}
}
func main()
{
let tree1: BinaryTree? = BinaryTree();
let tree2: BinaryTree = BinaryTree();
/*
1
/ \
2 8
/ \ /
3 10 6
/
7
-----------------------
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!.right!.left = TreeNode(6);
tree2.findDeepestNode(tree1!.root);
/*
1
/ \
2 8
/ \ / \
3 10 6 9
/ \
5 4
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = TreeNode(1);
tree2.root!.left = TreeNode(2);
tree2.root!.right = TreeNode(8);
tree2.root!.left!.left = TreeNode(3);
tree2.root!.left!.right = TreeNode(10);
tree2.root!.right!.left = TreeNode(6);
tree2.root!.right!.left!.left = TreeNode(5);
tree2.root!.right!.right = TreeNode(9);
tree2.root!.right!.right!.right = TreeNode(4);
// When more than one node exist in deepest level
// In above tree (5,4), Then pick first node
tree2.findDeepestNode(tree2.root);
}
main();
Output
Tree Node : 1 2 3 10 7 8 6
Deepest Node is : 7
Tree Node : 1 2 3 10 8 6 5 9 4
Deepest Node is : 5
/*
Kotlin Program
Find the deepest node in 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: Int;
var height: Int;
constructor()
{
this.root = null;
this.height = -1;
this.result = 0;
}
// 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);
}
}
// Find deepest node in binary tree
fun findDeepest(node: TreeNode ? , level : Int): Unit
{
if (node == null)
{
return;
}
// Reversibly, visit left and right subtree
this.findDeepest(node.left, level + 1);
this.findDeepest(node.right, level + 1);
if (level > this.height)
{
// When get a new higher level
this.height = level;
// Get node data
this.result = node.data;
}
}
// Handles the request of find the deepest node in a binary tree
fun findDeepestNode(root: TreeNode ? ): Unit
{
if (root == null)
{
print("\n Empty Tree\n");
return;
}
this.result = 0;
this.height = -1;
this.findDeepest(root, 0);
// Display tree elements
print("\n Tree Node : ");
this.preorder(root);
// Display deepest node
print("\n Deepest Node is : " + result + " \n");
}
}
fun main(args: Array < String > ): Unit
{
var tree1: BinaryTree = BinaryTree();
var tree2: BinaryTree = BinaryTree();
/*
1
/ \
2 8
/ \ /
3 10 6
/
7
-----------------------
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?.right?.left = TreeNode(6);
tree2.findDeepestNode(tree1.root);
/*
1
/ \
2 8
/ \ / \
3 10 6 9
/ \
5 4
-----------------------
Second Binary Tree
-----------------------
*/
tree2.root = TreeNode(1);
tree2.root?.left = TreeNode(2);
tree2.root?.right = TreeNode(8);
tree2.root?.left?.left = TreeNode(3);
tree2.root?.left?.right = TreeNode(10);
tree2.root?.right?.left = TreeNode(6);
tree2.root?.right?.left?.left = TreeNode(5);
tree2.root?.right?.right = TreeNode(9);
tree2.root?.right?.right?.right = TreeNode(4);
// When more than one node exist in deepest level
// In above tree (5,4), Then pick first node
tree2.findDeepestNode(tree2.root);
}
Output
Tree Node : 1 2 3 10 7 8 6
Deepest Node is : 7
Tree Node : 1 2 3 10 8 6 5 9 4
Deepest Node is : 5
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