Skip to main content

Find left leaf node in a binary search tree

Here given code implementation process.

//C Program 
//Find left leaf node in a binary search tree
#include <stdio.h>

#include <stdlib.h>
 //structure of Binary Search Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};
//Adding a new node in binary search tree
void add(struct Node **root, int data)
{
	//Create a dynamic node of binary search tree 
	struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
	if (new_node != NULL)
	{
		//Set data and pointer values
		new_node->data = data;
		new_node->left = NULL; //Initially node left-pointer is NULL
		new_node->right = NULL; //Initially node right-pointer is NULL
		if ( *root == NULL)
		{
			//When adds a first node in binary tree
			*root = new_node;
		}
		else
		{
			struct Node *find = *root;
			//iterate binary tree and add new node to proper position
			while (find != NULL)
			{
				if (find->data > data)
				{
					if (find->left == NULL)
					{
						find->left = new_node;
						break;
					}
					else
					{ //visit left sub-tree
						find = find->left;
					}
				}
				else
				{
					if (find->right == NULL)
					{
						find->right = new_node;
						break;
					}
					else
					{
						//visit right sub-tree
						find = find->right;
					}
				}
			}
		}
	}
	else
	{
		printf("Memory Overflow\n");
		exit(0); //Terminate program execution
	}
}
void left_leaf_nodes(struct Node *root)
{
	if (root != NULL)
	{
		if (root->left != NULL && root->left->left == NULL && root->left->right == NULL)
		{
			//When find left leaf node
			printf("  %d", root->left->data);
		}
		left_leaf_nodes(root->left);
		left_leaf_nodes(root->right);
	}
}
int main()
{
	struct Node *root = NULL;
	//Add nodes in binary search tree
	/*
	       17
	    /     \
	   4       19
	  / \     /  \
	 3   10  18   20
	    /  \        \
	   9    16       37
	*/
	add( & root, 17);
	add( & root, 4);
	add( & root, 3);
	add( & root, 10);
	add( & root, 19);
	add( & root, 18);
	add( & root, 20);
	add( & root, 37);
	add( & root, 16);
	add( & root, 9);
	left_leaf_nodes(root);
	return 0;
}

Output

  3  9  18
//Java Program 
//Find left leaf node in a binary search tree
//Binary Search Tree Node
class Node
{
	// Data value 
	public int data;
	// Indicates left and right subtree
	public Node left;
	public Node right;
	public Node(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	public Node root;
	public BinarySearchTree()
	{
		this.root = null;
	}
	//insert a binary search tree element
	public void add(int data)
	{
		//Create a dynamic node of binary search tree 
		Node new_node = new Node(data);
		if (new_node != null)
		{
			if (root == null)
			{
				//When add a first node in BST
				root = new_node;
			}
			else
			{
				Node find = root;
				//Add a new node to its proper position
				while (find != null)
				{
					if (find.data >= data)
					{
						if (find.left == null)
						{
							find.left = new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							find = find.left;
						}
					}
					else
					{
						if (find.right == null)
						{
							find.right = new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		}
		else
		{
			System.out.println("Memory Overflow");
		}
	}
	void left_leaf_nodes(Node root)
	{
		if (root != null)
		{
			if (root.left != null && root.left.left == null && root.left.right == null)
			{
				//When find left leaf node
				System.out.print("  " + root.left.data);
			}
			left_leaf_nodes(root.left);
			left_leaf_nodes(root.right);
		}
	}
	public static void main(String[] args)
	{
		BinarySearchTree obj = new BinarySearchTree();
		//Add nodes in binary search tree
		/*
		       17
		    /     \
		   4       19
		  / \     /  \
		 3   10  18   20
		    /  \        \
		   9    16       37
		*/
		obj.add(17);
		obj.add(4);
		obj.add(3);
		obj.add(10);
		obj.add(19);
		obj.add(18);
		obj.add(20);
		obj.add(37);
		obj.add(16);
		obj.add(9);
		obj.left_leaf_nodes(obj.root);
	}
}

Output

  3  9  18
//Include header file
#include <iostream>

using namespace std;
//C++ Program 
//Find left leaf node in a binary search tree
//Binary Search Tree Node
class Node
{
	public:
	// Data value 
	int data;
	// Indicates left and right subtree
	Node * left;
	Node * right;
	Node(int data)
	{
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinarySearchTree
{
	public: Node * root;
	BinarySearchTree()
	{
		this->root = NULL;
	}
	//insert a binary search tree element
	void add(int data)
	{
		//Create a dynamic node of binary search tree 
		Node * new_node = new Node(data);
		if (new_node != NULL)
		{
			if (this->root == NULL)
			{
				//When add a first node in BST
				this->root = new_node;
			}
			else
			{
				Node * find = this->root;
				//Add a new node to its proper position
				while (find != NULL)
				{
					if (find->data >= data)
					{
						if (find->left == NULL)
						{
							find->left = new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							find = find->left;
						}
					}
					else
					{
						if (find->right == NULL)
						{
							find->right = new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							find = find->right;
						}
					}
				}
			}
		}
		else
		{
			cout << "Memory Overflow";
		}
	}
	void left_leaf_nodes(Node * root)
	{
		if (root != NULL)
		{
			if (root->left != NULL && root->left->left == NULL && root->left->right == NULL)
			{
				//When find left leaf node
				cout << "  " << root->left->data;
			}
			this->left_leaf_nodes(root->left);
			this->left_leaf_nodes(root->right);
		}
	}
};
int main()
{
	BinarySearchTree obj = BinarySearchTree();
	//Add nodes in binary search tree
	/*
			       17
			    /     \
			   4       19
			  / \     /  \
			 3   10  18   20
			    /  \        \
			   9    16       37
			*/
	obj.add(17);
	obj.add(4);
	obj.add(3);
	obj.add(10);
	obj.add(19);
	obj.add(18);
	obj.add(20);
	obj.add(37);
	obj.add(16);
	obj.add(9);
	obj.left_leaf_nodes(obj.root);
	return 0;
}

Output

  3  9  18
//Include namespace system
using System;
//C# Program 
//Find left leaf node in a binary search tree
//Binary Search Tree Node
class Node
{
	// Data value 
	public int data;
	// Indicates left and right subtree
	public Node left;
	public Node right;
	public Node(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	public Node root;
	public BinarySearchTree()
	{
		this.root = null;
	}
	//insert a binary search tree element
	public void add(int data)
	{
		//Create a dynamic node of binary search tree 
		Node new_node = new Node(data);
		if (new_node != null)
		{
			if (root == null)
			{
				//When add a first node in BST
				root = new_node;
			}
			else
			{
				Node find = root;
				//Add a new node to its proper position
				while (find != null)
				{
					if (find.data >= data)
					{
						if (find.left == null)
						{
							find.left = new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							find = find.left;
						}
					}
					else
					{
						if (find.right == null)
						{
							find.right = new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		}
		else
		{
			Console.WriteLine("Memory Overflow");
		}
	}
	void left_leaf_nodes(Node root)
	{
		if (root != null)
		{
			if (root.left != null && root.left.left == null && root.left.right == null)
			{
				//When find left leaf node
				Console.Write("  " + root.left.data);
			}
			left_leaf_nodes(root.left);
			left_leaf_nodes(root.right);
		}
	}
	public static void Main(String[] args)
	{
		BinarySearchTree obj = new BinarySearchTree();
		//Add nodes in binary search tree
		/*
				       17
				    /     \
				   4       19
				  / \     /  \
				 3   10  18   20
				    /  \        \
				   9    16       37
				*/
		obj.add(17);
		obj.add(4);
		obj.add(3);
		obj.add(10);
		obj.add(19);
		obj.add(18);
		obj.add(20);
		obj.add(37);
		obj.add(16);
		obj.add(9);
		obj.left_leaf_nodes(obj.root);
	}
}

Output

  3  9  18
<?php
//Php Program 
//Find left leaf node in a binary search tree
//Binary Search Tree Node
class Node
{
	// Data value 
	public $data;
	// Indicates left and right subtree
	public $left;
	public $right;

	function __construct($data)
	{
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
class BinarySearchTree
{
	public $root;

	function __construct()
	{
		$this->root = null;
	}
	//insert a binary search tree element
	public	function add($data)
	{
		//Create a dynamic node of binary search tree 
		$new_node = new Node($data);
		if ($new_node != null)
		{
			if ($this->root == null)
			{
				//When add a first node in BST
				$this->root = $new_node;
			}
			else
			{
				$find = $this->root;
				//Add a new node to its proper position
				while ($find != null)
				{
					if ($find->data >= $data)
					{
						if ($find->left == null)
						{
							$find->left = $new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							$find = $find->left;
						}
					}
					else
					{
						if ($find->right == null)
						{
							$find->right = $new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							$find = $find->right;
						}
					}
				}
			}
		}
		else
		{
			echo "Memory Overflow";
		}
	}

	function left_leaf_nodes($root)
	{
		if ($root != null)
		{
			if ($root->left != null && $root->left->left == null && $root->left->right == null)
			{
				echo "  ". $root->left->data;
			}
			$this->left_leaf_nodes($root->left);
			$this->left_leaf_nodes($root->right);
		}
	}
}

function main()
{
	$obj = new BinarySearchTree();
	//Add nodes in binary search tree
	/*
			       17
			    /     \
			   4       19
			  / \     /  \
			 3   10  18   20
			    /  \        \
			   9    16       37
			*/
	$obj->add(17);
	$obj->add(4);
	$obj->add(3);
	$obj->add(10);
	$obj->add(19);
	$obj->add(18);
	$obj->add(20);
	$obj->add(37);
	$obj->add(16);
	$obj->add(9);
	$obj->left_leaf_nodes($obj->root);
}
main();

Output

  3  9  18
//Node Js Program 
//Find left leaf node in a binary search tree
//Binary Search Tree Node
class Node
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	constructor()
	{
		this.root = null;
	}
	//insert a binary search tree element
	add(data)
	{
		//Create a dynamic node of binary search tree 
		var new_node = new Node(data);
		if (new_node != null)
		{
			if (this.root == null)
			{
				//When add a first node in BST
				this.root = new_node;
			}
			else
			{
				var find = this.root;
				//Add a new node to its proper position
				while (find != null)
				{
					if (find.data >= data)
					{
						if (find.left == null)
						{
							find.left = new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							find = find.left;
						}
					}
					else
					{
						if (find.right == null)
						{
							find.right = new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		}
		else
		{
			process.stdout.write("Memory Overflow");
		}
	}
	left_leaf_nodes(root)
	{
		if (root != null)
		{
			if (root.left != null && root.left.left == null && root.left.right == null)
			{
				process.stdout.write("  " + root.left.data);
			}
			this.left_leaf_nodes(root.left);
			this.left_leaf_nodes(root.right);
		}
	}
}

function main()
{
	var obj = new BinarySearchTree();
	//Add nodes in binary search tree
	/*
			       17
			    /     \
			   4       19
			  / \     /  \
			 3   10  18   20
			    /  \        \
			   9    16       37
			*/
	obj.add(17);
	obj.add(4);
	obj.add(3);
	obj.add(10);
	obj.add(19);
	obj.add(18);
	obj.add(20);
	obj.add(37);
	obj.add(16);
	obj.add(9);
	obj.left_leaf_nodes(obj.root);
}
main();

Output

  3  9  18
# Python 3 Program 
# Find left leaf node in a binary search tree
# Binary Search Tree Node
class Node :
	#  Data value 
	
	#  Indicates left and right subtree
	
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
	

class BinarySearchTree :
	
	def __init__(self) :
		self.root = None
	
	# insert a binary search tree element
	def add(self, data) :
		# Create a dynamic node of binary search tree 
		new_node = Node(data)
		if (new_node != None) :
			if (self.root == None) :
				# When add a first node in BST
				self.root = new_node
			else :
				find = self.root
				# Add a new node to its proper position
				while (find != None) :
					if (find.data >= data) :
						if (find.left == None) :
							find.left = new_node
							return
						else :
							# visit left sub-tree
							find = find.left
						
					else :
						if (find.right == None) :
							find.right = new_node
							return
						else :
							# visit right sub-tree
							find = find.right
						
					
				
			
		else :
			print("Memory Overflow", end = "")
		
	
	def left_leaf_nodes(self, root) :
		if (root != None) :
			if (root.left != None and root.left.left == None and root.left.right == None) :
				print("  ", root.left.data, end = "")
			
			self.left_leaf_nodes(root.left)
			self.left_leaf_nodes(root.right)
		
	

def main() :
	obj = BinarySearchTree()
	# Add nodes in binary search tree
	# 
	# 		       17
	# 		    /     \
	# 		   4       19
	# 		  / \     /  \
	# 		 3   10  18   20
	# 		    /  \        \
	# 		   9    16       37
	# 		
	
	obj.add(17)
	obj.add(4)
	obj.add(3)
	obj.add(10)
	obj.add(19)
	obj.add(18)
	obj.add(20)
	obj.add(37)
	obj.add(16)
	obj.add(9)
	obj.left_leaf_nodes(obj.root)

if __name__ == "__main__": main()

Output

   3   9   18
# Ruby Program 
# Find left leaf node in a binary search tree
# Binary Search Tree Node
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right


	#  Data value 
	
	#  Indicates left and right subtree
	
	def initialize(data)
	
		self.data = data
		self.left = nil
		self.right = nil
	end
end
class BinarySearchTree 

	# Define the accessor and reader of class BinarySearchTree  
	attr_reader :root
	attr_accessor :root


	
	def initialize()
	
		self.root = nil
	end
	# insert a binary search tree element
	def add(data)
	
		# Create a dynamic node of binary search tree 
		new_node = Node.new(data)
		if (new_node != nil)
		
			if (@root == nil)
			
				# When add a first node in BST
				@root = new_node
			else
			
				find = @root
				# Add a new node to its proper position
				while (find != nil)
				
					if (find.data >= data)
					
						if (find.left == nil)
						
							find.left = new_node
							return
						else
						
							# visit left sub-tree
							find = find.left
						end
					else
					
						if (find.right == nil)
						
							find.right = new_node
							return
						else
						
							# visit right sub-tree
							find = find.right
						end
					end
				end
			end
		else
		
			print("Memory Overflow")
		end
	end
	def left_leaf_nodes(root)
	
		if (root != nil)
		
			if (root.left != nil && root.left.left == nil && root.left.right == nil)
			
				# When find left leaf node
				print("  ", root.left.data)
			end
			self.left_leaf_nodes(root.left)
			self.left_leaf_nodes(root.right)
		end
	end
end
def main()

	obj = BinarySearchTree.new()
	# Add nodes in binary search tree
	# 
	# 		       17
	# 		    /     \
	# 		   4       19
	# 		  / \     /  \
	# 		 3   10  18   20
	# 		    /  \        \
	# 		   9    16       37
	# 		
	
	obj.add(17)
	obj.add(4)
	obj.add(3)
	obj.add(10)
	obj.add(19)
	obj.add(18)
	obj.add(20)
	obj.add(37)
	obj.add(16)
	obj.add(9)
	obj.left_leaf_nodes(obj.root)
end
main()

Output

  3  9  18
//Scala Program 
//Find left leaf node in a binary search tree
//Binary Search Tree Node
class Node(var data: Int,
	var left: Node,
		var right: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class BinarySearchTree(var root: Node)
{
	def this()
	{
		this(null);
	}
	//insert a binary search tree element
	def add(data: Int): Unit = {
		//Create a dynamic node of binary search tree 
		var new_node: Node = new Node(data);
		if (new_node != null)
		{
			if (root == null)
			{
				//When add a first node in BST
				root = new_node;
			}
			else
			{
				var find: Node = root;
				//Add a new node to its proper position
				while (find != null)
				{
					if (find.data >= data)
					{
						if (find.left == null)
						{
							find.left = new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							find = find.left;
						}
					}
					else
					{
						if (find.right == null)
						{
							find.right = new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		}
		else
		{
			print("Memory Overflow");
		}
	}
	def left_leaf_nodes(root: Node): Unit = {
		if (root != null)
		{
			if (root.left != null && root.left.left == null && root.left.right == null)
			{
				//When find left leaf node
				print("  " + root.left.data);
			}
			left_leaf_nodes(root.left);
			left_leaf_nodes(root.right);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: BinarySearchTree = new BinarySearchTree();
		//Add nodes in binary search tree
		/*
				       17
				    /     \
				   4       19
				  / \     /  \
				 3   10  18   20
				    /  \        \
				   9    16       37
				*/
		obj.add(17);
		obj.add(4);
		obj.add(3);
		obj.add(10);
		obj.add(19);
		obj.add(18);
		obj.add(20);
		obj.add(37);
		obj.add(16);
		obj.add(9);
		obj.left_leaf_nodes(obj.root);
	}
}

Output

  3  9  18
//Swift Program 
//Find left leaf node in a binary search tree
//Binary Search Tree Node
class Node
{
	// Data value 
	var data: Int;
	// Indicates left and right subtree
	var left: Node? ;
	var right: Node? ;
	init(_ data: Int)
	{
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinarySearchTree
{
	var root: Node? ;
	init()
	{
		self.root = nil;
	}
	//insert a binary search tree element
	func add(_ data: Int)
	{
		//Create a dynamic node of binary search tree 
		let new_node: Node? = Node(data);
		if (new_node != nil)
		{
			if (self.root == nil)
			{
				//When add a first node in BST
				self.root = new_node;
			}
			else
			{
				var find: Node? = self.root;
				//Add a new node to its proper position
				while (find != nil)
				{
					if (find!.data >= data)
					{
						if (find!.left == nil)
						{
							find!.left = new_node;
							return;
						}
						else
						{
							//visit left sub-tree
							find = find!.left;
						}
					}
					else
					{
						if (find!.right == nil)
						{
							find!.right = new_node;
							return;
						}
						else
						{
							//visit right sub-tree
							find = find!.right;
						}
					}
				}
			}
		}
		else
		{
			print("Memory Overflow", terminator: "");
		}
	}
	func left_leaf_nodes(_ root: Node? )
	{
		if (root != nil)
		{
			if (root!.left != nil && root!.left!.left == nil && root!.left!.right == nil)
			{
				print("  ", root!.left!.data, terminator: "");
			}
			self.left_leaf_nodes(root!.left);
			self.left_leaf_nodes(root!.right);
		}
	}
}
func main()
{
	let obj: BinarySearchTree = BinarySearchTree();
	//Add nodes in binary search tree
	/*
			       17
			    /     \
			   4       19
			  / \     /  \
			 3   10  18   20
			    /  \        \
			   9    16       37
			*/
	obj.add(17);
	obj.add(4);
	obj.add(3);
	obj.add(10);
	obj.add(19);
	obj.add(18);
	obj.add(20);
	obj.add(37);
	obj.add(16);
	obj.add(9);
	obj.left_leaf_nodes(obj.root);
}
main();

Output

   3   9   18
Last updated on by Kalkicode




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