Find parent of leaf nodes in binary tree

Here given code implementation process.

// C program for
// Find parent of leaf nodes 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 a dynamic tree 
	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;
}
// This is creates and returns the new binary tree node
struct TreeNode *getNode(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;
}
//  Find the parent of leaf nodes using recursion
void leafParent(struct TreeNode *node, struct TreeNode *parent)
{
	if (node != NULL)
	{
		// Check that node is leaf node or not
		if ((node->left == NULL && node->right == NULL))
		{
			if (parent == NULL)
			{
				// When one node of tree
				printf(" NULL ");
			}
			else
			{
				printf("  %d", parent->data);
			}
		}
		else
		{
			// Visit left subtree
			leafParent(node->left, node);
			// Visit right subtree
			leafParent(node->right, node);
		}
	}
}
int main(int argc, char const *argv[])
{
	struct BinaryTree *tree = newTree();
	/*
	        34                            
	       /   \    
	     -4     10    
	     / \      \               
	    7   12     6
	   /   / \     
	  4   6   8   
	     / \      
	    9   1       
	-----------------
	  Constructing binary tree
	*/
	tree->root = getNode(34);
	tree->root->left = getNode(-4);
	tree->root->left->right = getNode(12);
	tree->root->left->right->left = getNode(6);
	tree->root->left->right->left->left = getNode(9);
	tree->root->left->right->left->right = getNode(1);
	tree->root->left->right->right = getNode(8);
	tree->root->left->left = getNode(7);
	tree->root->left->left->left = getNode(4);
	tree->root->right = getNode(10);
	tree->root->right->right = getNode(6);
	leafParent(tree->root, NULL);
	return 0;
}

input

  7  6  6  12  10
/*
    Java Program
    Find parent of leaf nodes in binary tree
*/
// Binary Tree node
class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
	}
	//  Find the parent of leaf nodes using recursion
	public void leafParent(TreeNode node, TreeNode parent)
	{
		if (node != null)
		{
			// Check that node is leaf node or not
			if ((node.left == null && node.right == null))
			{
				if (parent == null)
				{
					// When one node of tree
					System.out.print(" NULL ");
				}
				else
				{
					System.out.print(" " + parent.data );
				}
			}
			else
			{
				// Visit left subtree
				leafParent(node.left, node);
				// Visit right subtree
				leafParent(node.right, node);
			}
		}
	}
	public static void main(String[] args)
	{
		// Create new binary trees 
		BinaryTree tree = new BinaryTree();
		/*
		        34                            
		       /   \    
		     -4     10    
		     / \      \               
		    7   12     6
		   /   / \     
		  4   6   8   
		     / \      
		    9   1       
		-----------------
		  Constructing binary tree
		*/
		tree.root = new TreeNode(34);
		tree.root.left = new TreeNode(-4);
		tree.root.left.right = new TreeNode(12);
		tree.root.left.right.left = new TreeNode(6);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.left.right.left.right = new TreeNode(1);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.left = new TreeNode(7);
		tree.root.left.left.left = new TreeNode(4);
		tree.root.right = new TreeNode(10);
		tree.root.right.right = new TreeNode(6);
		tree.leafParent(tree.root, null);
	}
}

input

 7 6 6 12 10
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program
    Find parent of leaf nodes in binary tree
*/
// Binary Tree node
class TreeNode
{
	public: int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		// Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinaryTree
{
	public: TreeNode *root;
	BinaryTree()
	{
		this->root = NULL;
	}
	//  Find the parent of leaf nodes using recursion
	void leafParent(TreeNode *node, TreeNode *parent)
	{
		if (node != NULL)
		{
			// Check that node is leaf node or not
			if ((node->left == NULL && node->right == NULL))
			{
				if (parent == NULL)
				{
					// When one node of tree
					cout << " NULL ";
				}
				else
				{
					cout << " " << parent->data;
				}
			}
			else
			{
				// Visit left subtree
				this->leafParent(node->left, node);
				// Visit right subtree
				this->leafParent(node->right, node);
			}
		}
	}
};
int main()
{
	// Create new binary trees
	BinaryTree *tree = new BinaryTree();
	/*
	        34                            
	       /   \    
	     -4     10    
	     / \      \               
	    7   12     6
	   /   / \     
	  4   6   8   
	     / \      
	    9   1       
	-----------------
	  Constructing binary tree
	*/
	tree->root = new TreeNode(34);
	tree->root->left = new TreeNode(-4);
	tree->root->left->right = new TreeNode(12);
	tree->root->left->right->left = new TreeNode(6);
	tree->root->left->right->left->left = new TreeNode(9);
	tree->root->left->right->left->right = new TreeNode(1);
	tree->root->left->right->right = new TreeNode(8);
	tree->root->left->left = new TreeNode(7);
	tree->root->left->left->left = new TreeNode(4);
	tree->root->right = new TreeNode(10);
	tree->root->right->right = new TreeNode(6);
	tree->leafParent(tree->root, NULL);
	return 0;
}

input

 7 6 6 12 10
// Include namespace system
using System;
/*
    Csharp Program
    Find parent of leaf nodes in binary tree
*/
// Binary Tree node
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
	}
	//  Find the parent of leaf nodes using recursion
	public void leafParent(TreeNode node, TreeNode parent)
	{
		if (node != null)
		{
			// Check that node is leaf node or not
			if ((node.left == null && node.right == null))
			{
				if (parent == null)
				{
					// When one node of tree
					Console.Write(" NULL ");
				}
				else
				{
					Console.Write(" " + parent.data);
				}
			}
			else
			{
				// Visit left subtree
				this.leafParent(node.left, node);
				// Visit right subtree
				this.leafParent(node.right, node);
			}
		}
	}
	public static void Main(String[] args)
	{
		// Create new binary trees
		BinaryTree tree = new BinaryTree();
		/*
		        34                            
		       /   \    
		     -4     10    
		     / \      \               
		    7   12     6
		   /   / \     
		  4   6   8   
		     / \      
		    9   1       
		-----------------
		  Constructing binary tree
		*/
		tree.root = new TreeNode(34);
		tree.root.left = new TreeNode(-4);
		tree.root.left.right = new TreeNode(12);
		tree.root.left.right.left = new TreeNode(6);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.left.right.left.right = new TreeNode(1);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.left = new TreeNode(7);
		tree.root.left.left.left = new TreeNode(4);
		tree.root.right = new TreeNode(10);
		tree.root.right.right = new TreeNode(6);
		tree.leafParent(tree.root, null);
	}
}

input

 7 6 6 12 10
<?php
/*
    Php Program
    Find parent of leaf nodes in binary tree
*/
// Binary Tree node
class TreeNode
{
	public $data;
	public $left;
	public $right;
	public	function __construct($data)
	{
		// Set node value
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class BinaryTree
{
	public $root;
	public	function __construct()
	{
		$this->root = NULL;
	}
	//  Find the parent of leaf nodes using recursion
	public	function leafParent($node, $parent)
	{
		if ($node != NULL)
		{
			// Check that node is leaf node or not
			if (($node->left == NULL && $node->right == NULL))
			{
				if ($parent == NULL)
				{
					// When one node of tree
					echo(" NULL ");
				}
				else
				{
					echo(" ".$parent->data);
				}
			}
			else
			{
				// Visit left subtree
				$this->leafParent($node->left, $node);
				// Visit right subtree
				$this->leafParent($node->right, $node);
			}
		}
	}
}

function main()
{
	// Create new binary trees
	$tree = new BinaryTree();
	/*
	        34                            
	       /   \    
	     -4     10    
	     / \      \               
	    7   12     6
	   /   / \     
	  4   6   8   
	     / \      
	    9   1       
	-----------------
	  Constructing binary tree
	*/
	$tree->root = new TreeNode(34);
	$tree->root->left = new TreeNode(-4);
	$tree->root->left->right = new TreeNode(12);
	$tree->root->left->right->left = new TreeNode(6);
	$tree->root->left->right->left->left = new TreeNode(9);
	$tree->root->left->right->left->right = new TreeNode(1);
	$tree->root->left->right->right = new TreeNode(8);
	$tree->root->left->left = new TreeNode(7);
	$tree->root->left->left->left = new TreeNode(4);
	$tree->root->right = new TreeNode(10);
	$tree->root->right->right = new TreeNode(6);
	$tree->leafParent($tree->root, NULL);
}
main();

input

 7 6 6 12 10
/*
    Node JS Program
    Find parent of leaf nodes in binary tree
*/
// Binary Tree node
class TreeNode
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
	}
	//  Find the parent of leaf nodes using recursion
	leafParent(node, parent)
	{
		if (node != null)
		{
			// Check that node is leaf node or not
			if ((node.left == null && node.right == null))
			{
				if (parent == null)
				{
					// When one node of tree
					process.stdout.write(" NULL ");
				}
				else
				{
					process.stdout.write(" " + parent.data);
				}
			}
			else
			{
				// Visit left subtree
				this.leafParent(node.left, node);
				// Visit right subtree
				this.leafParent(node.right, node);
			}
		}
	}
}

function main()
{
	// Create new binary trees
	var tree = new BinaryTree();
	/*
	        34                            
	       /   \    
	     -4     10    
	     / \      \               
	    7   12     6
	   /   / \     
	  4   6   8   
	     / \      
	    9   1       
	-----------------
	  Constructing binary tree
	*/
	tree.root = new TreeNode(34);
	tree.root.left = new TreeNode(-4);
	tree.root.left.right = new TreeNode(12);
	tree.root.left.right.left = new TreeNode(6);
	tree.root.left.right.left.left = new TreeNode(9);
	tree.root.left.right.left.right = new TreeNode(1);
	tree.root.left.right.right = new TreeNode(8);
	tree.root.left.left = new TreeNode(7);
	tree.root.left.left.left = new TreeNode(4);
	tree.root.right = new TreeNode(10);
	tree.root.right.right = new TreeNode(6);
	tree.leafParent(tree.root, null);
}
main();

input

 7 6 6 12 10
#    Python 3 Program
#    Find parent of leaf nodes in binary tree

#  Binary Tree node
class TreeNode :
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

class BinaryTree :
	def __init__(self) :
		self.root = None
	
	#   Find the parent of leaf nodes using recursion
	def leafParent(self, node, parent) :
		if (node != None) :
			#  Check that node is leaf node or not
			if ((node.left == None and node.right == None)) :
				if (parent == None) :
					#  When one node of tree
					print(" NULL ", end = "")
				else :
					print(" ", parent.data, end = "")
				
			else :
				#  Visit left subtree
				self.leafParent(node.left, node)
				#  Visit right subtree
				self.leafParent(node.right, node)
			
		
	

def main() :
	#  Create new binary trees
	tree = BinaryTree()
	#        34                            
	#       /   \    
	#     -4     10    
	#     / \      \               
	#    7   12     6
	#   /   / \     
	#  4   6   8   
	#     / \      
	#    9   1       
	# -----------------
	#  Constructing binary tree
	tree.root = TreeNode(34)
	tree.root.left = TreeNode(-4)
	tree.root.left.right = TreeNode(12)
	tree.root.left.right.left = TreeNode(6)
	tree.root.left.right.left.left = TreeNode(9)
	tree.root.left.right.left.right = TreeNode(1)
	tree.root.left.right.right = TreeNode(8)
	tree.root.left.left = TreeNode(7)
	tree.root.left.left.left = TreeNode(4)
	tree.root.right = TreeNode(10)
	tree.root.right.right = TreeNode(6)
	tree.leafParent(tree.root, None)

if __name__ == "__main__": main()

input

  7  6  6  12  10
#    Ruby Program
#    Find parent of leaf nodes in binary tree

#  Binary 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) 
		#  Set node value
		self.data = data
		self.left = nil
		self.right = nil
	end

end

class BinaryTree 
	# Define the accessor and reader of class BinaryTree
	attr_reader :root
	attr_accessor :root
	def initialize() 
		self.root = nil
	end

	#   Find the parent of leaf nodes using recursion
	def leafParent(node, parent) 
		if (node != nil) 
			#  Check that node is leaf node or not
			if ((node.left == nil && node.right == nil)) 
				if (parent == nil) 
					#  When one node of tree
					print(" NULL ")
				else
 
					print(" ", parent.data)
				end

			else
 
				#  Visit left subtree
				self.leafParent(node.left, node)
				#  Visit right subtree
				self.leafParent(node.right, node)
			end

		end

	end

end

def main() 
	#  Create new binary trees
	tree = BinaryTree.new()
	#        34                            
	#       /   \    
	#     -4     10    
	#     / \      \               
	#    7   12     6
	#   /   / \     
	#  4   6   8   
	#     / \      
	#    9   1       
	# -----------------
	#  Constructing binary tree
	tree.root = TreeNode.new(34)
	tree.root.left = TreeNode.new(-4)
	tree.root.left.right = TreeNode.new(12)
	tree.root.left.right.left = TreeNode.new(6)
	tree.root.left.right.left.left = TreeNode.new(9)
	tree.root.left.right.left.right = TreeNode.new(1)
	tree.root.left.right.right = TreeNode.new(8)
	tree.root.left.left = TreeNode.new(7)
	tree.root.left.left.left = TreeNode.new(4)
	tree.root.right = TreeNode.new(10)
	tree.root.right.right = TreeNode.new(6)
	tree.leafParent(tree.root, nil)
end

main()

input

 7 6 6 12 10
/*
    Scala Program
    Find parent of leaf nodes in binary tree
*/
// Binary Tree node
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		// Set node value
		this(data, null, null);
	}
}
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	//  Find the parent of leaf nodes using recursion
	def leafParent(node: TreeNode, parent: TreeNode): Unit = {
		if (node != null)
		{
			// Check that node is leaf node or not
			if ((node.left == null && node.right == null))
			{
				if (parent == null)
				{
					// When one node of tree
					print(" NULL ");
				}
				else
				{
					print(" " + parent.data);
				}
			}
			else
			{
				// Visit left subtree
				leafParent(node.left, node);
				// Visit right subtree
				leafParent(node.right, node);
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create new binary trees
		var tree: BinaryTree = new BinaryTree();
		/*
		        34                            
		       /   \    
		     -4     10    
		     / \      \               
		    7   12     6
		   /   / \     
		  4   6   8   
		     / \      
		    9   1       
		-----------------
		  Constructing binary tree
		*/
		tree.root = new TreeNode(34);
		tree.root.left = new TreeNode(-4);
		tree.root.left.right = new TreeNode(12);
		tree.root.left.right.left = new TreeNode(6);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.left.right.left.right = new TreeNode(1);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.left = new TreeNode(7);
		tree.root.left.left.left = new TreeNode(4);
		tree.root.right = new TreeNode(10);
		tree.root.right.right = new TreeNode(6);
		tree.leafParent(tree.root, null);
	}
}

input

 7 6 6 12 10
/*
    Swift 4 Program
    Find parent of leaf nodes in binary tree
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		// Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	//  Find the parent of leaf nodes using recursion
	func leafParent(_ node: TreeNode? , _ parent : TreeNode? )
	{
		if (node  != nil)
		{
			// Check that node is leaf node or not
			if ((node!.left == nil && node!.right == nil))
			{
				if (parent == nil)
				{
					// When one node of tree
					print(" NULL ", terminator: "");
				}
				else
				{
					print(" ", parent!.data, terminator: "");
				}
			}
			else
			{
				// Visit left subtree
				self.leafParent(node!.left, node);
				// Visit right subtree
				self.leafParent(node!.right, node);
			}
		}
	}
}
func main()
{
	// Create new binary trees
	let tree = BinaryTree();
	/*
	        34                            
	       /   \    
	     -4     10    
	     / \      \               
	    7   12     6
	   /   / \     
	  4   6   8   
	     / \      
	    9   1       
	-----------------
	  Constructing binary tree
	*/
	tree.root = TreeNode(34);
	tree.root!.left = TreeNode(-4);
	tree.root!.left!.right = TreeNode(12);
	tree.root!.left!.right!.left = TreeNode(6);
	tree.root!.left!.right!.left!.left = TreeNode(9);
	tree.root!.left!.right!.left!.right = TreeNode(1);
	tree.root!.left!.right!.right = TreeNode(8);
	tree.root!.left!.left = TreeNode(7);
	tree.root!.left!.left!.left = TreeNode(4);
	tree.root!.right = TreeNode(10);
	tree.root!.right!.right = TreeNode(6);
	tree.leafParent(tree.root, nil);
}
main();

input

  7  6  6  12  10
/*
    Kotlin Program
    Find parent of leaf nodes in binary tree
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	//  Find the parent of leaf nodes using recursion
	fun leafParent(node: TreeNode ? , parent : TreeNode ? ): Unit
	{
		if (node != null)
		{
			// Check that node is leaf node or not
			if ((node.left == null && node.right == null))
			{
				if (parent == null)
				{
					// When one node of tree
					print(" NULL ");
				}
				else
				{
					print(" " + parent.data);
				}
			}
			else
			{
				// Visit left subtree
				this.leafParent(node.left, node);
				// Visit right subtree
				this.leafParent(node.right, node);
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Create new binary trees
	val tree: BinaryTree = BinaryTree();
	/*
	        34                            
	       /   \    
	     -4     10    
	     / \      \               
	    7   12     6
	   /   / \     
	  4   6   8   
	     / \      
	    9   1       
	-----------------
	  Constructing binary tree
	*/
	tree.root = TreeNode(34);
	tree.root?.left = TreeNode(-4);
	tree.root?.left?.right = TreeNode(12);
	tree.root?.left?.right?.left = TreeNode(6);
	tree.root?.left?.right?.left?.left = TreeNode(9);
	tree.root?.left?.right?.left?.right = TreeNode(1);
	tree.root?.left?.right?.right = TreeNode(8);
	tree.root?.left?.left = TreeNode(7);
	tree.root?.left?.left?.left = TreeNode(4);
	tree.root?.right = TreeNode(10);
	tree.root?.right?.right = TreeNode(6);
	tree.leafParent(tree.root, null);
}

input

 7 6 6 12 10


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







© 2021, kalkicode.com, All rights reserved