Posted on by Kalkicode
Code Binary Tree

Find the deepest node in binary tree

Find a deepest leaf 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

Comment

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