Skip to main content

Find nth node in preorder traversal

Here given code implementation process.

/*
    C Program 
    Find nth node in preorder traversal
*/
#include <stdio.h>
#include <stdlib.h>

//Binary Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};
//This is creating a binary tree node and return this
struct Node *get_node(int data)
{
	// Create dynamic node
	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;
		new_node->right = NULL;
	}
	else
	{
		//This is indicates, segmentation fault or memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return new_node;
}
//Display pre order elements
void preorder(struct Node *node)
{
	if (node != NULL)
	{
		//Print node value
		printf("  %d", node->data);
		preorder(node->left);
		preorder(node->right);
	}
}
// Find nth node in preorder
struct Node *find_nth_preorder(struct Node *node, int n, int *position)
{
	if (node == NULL)
	{
		return NULL;
	}*position = *position + 1;
	if (n == *position)
	{
		// When get Nth preorder node
		return node;
	}
	struct Node *result = find_nth_preorder(node->left, n, position);
	if (result == NULL)
	{
		result = find_nth_preorder(node->right, n, position);
	}
	return result;
}
// Handles the request to find nth nodes in preorder traversal
void find_node(struct Node *root, int n)
{
	if (n <= 0)
	{
		//Invalid node
		return;
	}
	else if (root == NULL)
	{
		printf("\n Empty Tree\n");
	}
	else
	{
		int position = 0;
		struct Node *result = find_nth_preorder(root, n, & position);
		if (result != NULL)
		{
			// Print nth node
			printf(" [%d-th] Preorder node is : %d\n", n, result->data);
		}
		else
		{
			printf(" [%d-th] Preorder node not exists \n", n);
		}
	}
}
int main()
{
	struct Node *root = NULL;
	/*
	constructor binary tree
	-----------------
	     80                            
	   /   \    
	  5     7    
	 / \     \               
	1   3     2  
	   / \     \
	  10  8     9
	     / \
	    12  4

	-----------------
	*/
	root = get_node(80);
	root->left = get_node(5);
	root->left->right = get_node(3);
	root->left->right->left = get_node(10);
	root->left->right->right = get_node(8);
	root->left->right->right->left = get_node(12);
	root->left->right->right->right = get_node(4);
	root->left->left = get_node(1);
	root->right = get_node(7);
	root->right->right = get_node(2);
	root->right->right->right = get_node(9);
	printf("\n Tree Nodes \n");
	preorder(root);
	printf("\n");
	//Test Case
	find_node(root, 4);
	find_node(root, 1);
	find_node(root, 3);
	find_node(root, 11);
	find_node(root, 5);
	find_node(root, 17);
	return 0;
}

Output

 Tree Nodes
  80  5  1  3  10  8  12  4  7  2  9
 [4-th] Preorder node is : 3
 [1-th] Preorder node is : 80
 [3-th] Preorder node is : 1
 [11-th] Preorder node is : 9
 [5-th] Preorder node is : 10
 [17-th] Preorder node not exists
/*
    Java Program 
    Find nth node in preorder traversal
*/

// Binary Tree node
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public Node root;
	public int position;
	public BinaryTree()
	{
		//Set initial tree root to null
		this.root = null;
		this.position = 0;
	}
	//Display pre order elements
	public void preorder(Node node)
	{
		if (node != null)
		{
			//Print node value
			System.out.print("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	// Find nth node in preorder
	public Node find_nth_preorder(Node node, int n)
	{
		if (node == null)
		{
			return null;
		}
		this.position = this.position + 1;
		if (n == this.position)
		{
			// When get Nth preorder node
			return node;
		}
		Node result = find_nth_preorder(node.left, n);
		if (result == null)
		{
			result = find_nth_preorder(node.right, n);
		}
		return result;
	}
	// Handles the request to find nth nodes in preorder traversal
	public void find_node(int n)
	{
		if (n <= 0)
		{
			//Invalid node
			return;
		}
		else if (this.root == null)
		{
			System.out.print("\n Empty Tree\n");
		}
		else
		{
			this.position = 0;
			Node result = find_nth_preorder(this.root, n);
			if (result != null)
			{
				// Print nth node
				System.out.print(" [" + n + "-th] Preorder node is : " + result.data + "\n");
			}
			else
			{
				System.out.print(" [" + n + "-th] Preorder node not exists \n");
			}
		}
	}
	public static void main(String[] args)
	{
		//Create tree object
		BinaryTree tree = new BinaryTree();
		/*
		constructor binary tree
		-----------------
		     80                            
		   /   \    
		  5     7    
		 / \     \               
		1   3     2  
		   / \     \
		  10  8     9
		     / \
		    12  4

		-----------------
		*/
		tree.root = new Node(80);
		tree.root.left = new Node(5);
		tree.root.left.right = new Node(3);
		tree.root.left.right.left = new Node(10);
		tree.root.left.right.right = new Node(8);
		tree.root.left.right.right.left = new Node(12);
		tree.root.left.right.right.right = new Node(4);
		tree.root.left.left = new Node(1);
		tree.root.right = new Node(7);
		tree.root.right.right = new Node(2);
		tree.root.right.right.right = new Node(9);
		System.out.print("\n Tree Nodes \n");
		tree.preorder(tree.root);
		System.out.print("\n");
		//Test Case
		tree.find_node(4);
		tree.find_node(1);
		tree.find_node(3);
		tree.find_node(11);
		tree.find_node(5);
		tree.find_node(17);
	}
}

Output

 Tree Nodes
  80  5  1  3  10  8  12  4  7  2  9
 [4-th] Preorder node is : 3
 [1-th] Preorder node is : 80
 [3-th] Preorder node is : 1
 [11-th] Preorder node is : 9
 [5-th] Preorder node is : 10
 [17-th] Preorder node not exists
// Include header file
#include <iostream>
using namespace std;

/*
     C++ Program 
     Find nth node in preorder traversal
*/

//  Binary Tree node
class Node
{
	public: int data;
	Node *left;
	Node *right;
	Node(int data)
	{
		//  Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinaryTree
{
	public: Node *root;
	int position;
	BinaryTree()
	{
		// Set initial tree root to null
		this->root = NULL;
		this->position = 0;
	}
	// Display pre order elements
	void preorder(Node *node)
	{
		if (node != NULL)
		{
			// Print node value
			cout << "  " << node->data;
			this->preorder(node->left);
			this->preorder(node->right);
		}
	}
	//  Find nth node in preorder
	Node *find_nth_preorder(Node *node, int n)
	{
		if (node == NULL)
		{
			return NULL;
		}
		this->position = this->position + 1;
		if (n == this->position)
		{
			//  When get Nth preorder node
			return node;
		}
		Node *result = this->find_nth_preorder(node->left, n);
		if (result == NULL)
		{
			result = this->find_nth_preorder(node->right, n);
		}
		return result;
	}
	//  Handles the request to find nth nodes in preorder traversal
	void find_node(int n)
	{
		// Invalid node
		if (n <= 0)
		{
			return;
		}
		else if (this->root == NULL)
		{
			cout << "\n Empty Tree\n";
		}
		else
		{
			this->position = 0;
			Node *result = this->find_nth_preorder(this->root, n);
			if (result != NULL)
			{
				//  Print nth node
				cout << " [" << n << "-th] Preorder node is : " << result->data << "\n";
			}
			else
			{
				cout << " [" << n << "-th] Preorder node not exists \n";
			}
		}
	}
};
int main()
{
	// Create tree object
	BinaryTree tree = BinaryTree();
	/*
	  		constructor binary tree
	  		-----------------
	  		     80                            
	  		   /   \    
	  		  5     7    
	  		 / \     \               
	  		1   3     2  
	  		   / \     \
	  		  10  8     9
	  		     / \
	  		    12  4
	  		-----------------
	*/
	tree.root = new Node(80);
	tree.root->left = new Node(5);
	tree.root->left->right = new Node(3);
	tree.root->left->right->left = new Node(10);
	tree.root->left->right->right = new Node(8);
	tree.root->left->right->right->left = new Node(12);
	tree.root->left->right->right->right = new Node(4);
	tree.root->left->left = new Node(1);
	tree.root->right = new Node(7);
	tree.root->right->right = new Node(2);
	tree.root->right->right->right = new Node(9);
	cout << "\n Tree Nodes \n";
	tree.preorder(tree.root);
	cout << "\n";
	// Test Case
	tree.find_node(4);
	tree.find_node(1);
	tree.find_node(3);
	tree.find_node(11);
	tree.find_node(5);
	tree.find_node(17);
	return 0;
}

Output

 Tree Nodes
  80  5  1  3  10  8  12  4  7  2  9
 [4-th] Preorder node is : 3
 [1-th] Preorder node is : 80
 [3-th] Preorder node is : 1
 [11-th] Preorder node is : 9
 [5-th] Preorder node is : 10
 [17-th] Preorder node not exists
// Include namespace system
using System;

/*
     C# Program 
     Find nth node in preorder traversal
*/

//  Binary Tree node
public class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		//  Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public Node root;
	public int position;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
		this.position = 0;
	}
	// Display pre order elements
	public void preorder(Node node)
	{
		if (node != null)
		{
			// Print node value
			Console.Write("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	//  Find nth node in preorder
	public Node find_nth_preorder(Node node, int n)
	{
		if (node == null)
		{
			return null;
		}
		this.position = this.position + 1;
		if (n == this.position)
		{
			//  When get Nth preorder node
			return node;
		}
		Node result = find_nth_preorder(node.left, n);
		if (result == null)
		{
			result = find_nth_preorder(node.right, n);
		}
		return result;
	}
	//  Handles the request to find nth nodes in preorder traversal
	public void find_node(int n)
	{
		// Invalid node
		if (n <= 0)
		{
			return;
		}
		else if (this.root == null)
		{
			Console.Write("\n Empty Tree\n");
		}
		else
		{
			this.position = 0;
			Node result = find_nth_preorder(this.root, n);
			if (result != null)
			{
				//  Print nth node
				Console.Write(" [" + n + "-th] Preorder node is : " + result.data + "\n");
			}
			else
			{
				Console.Write(" [" + n + "-th] Preorder node not exists \n");
			}
		}
	}
	public static void Main(String[] args)
	{
		// Create tree object
		BinaryTree tree = new BinaryTree();
		/*
		  		constructor binary tree
		  		-----------------
		  		     80                            
		  		   /   \    
		  		  5     7    
		  		 / \     \               
		  		1   3     2  
		  		   / \     \
		  		  10  8     9
		  		     / \
		  		    12  4
		  		-----------------
		*/
		tree.root = new Node(80);
		tree.root.left = new Node(5);
		tree.root.left.right = new Node(3);
		tree.root.left.right.left = new Node(10);
		tree.root.left.right.right = new Node(8);
		tree.root.left.right.right.left = new Node(12);
		tree.root.left.right.right.right = new Node(4);
		tree.root.left.left = new Node(1);
		tree.root.right = new Node(7);
		tree.root.right.right = new Node(2);
		tree.root.right.right.right = new Node(9);
		Console.Write("\n Tree Nodes \n");
		tree.preorder(tree.root);
		Console.Write("\n");
		// Test Case
		tree.find_node(4);
		tree.find_node(1);
		tree.find_node(3);
		tree.find_node(11);
		tree.find_node(5);
		tree.find_node(17);
	}
}

Output

 Tree Nodes
  80  5  1  3  10  8  12  4  7  2  9
 [4-th] Preorder node is : 3
 [1-th] Preorder node is : 80
 [3-th] Preorder node is : 1
 [11-th] Preorder node is : 9
 [5-th] Preorder node is : 10
 [17-th] Preorder node not exists
<?php
/*
     Php Program 
     Find nth node in preorder traversal
*/

//  Binary Tree node
class Node
{
	public $data;
	public $left;
	public $right;

	function __construct($data)
	{
		//  Set node value
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
class BinaryTree
{
	public $root;
	public $position;

	function __construct()
	{
		// Set initial tree root to null
		$this->root = null;
		$this->position = 0;
	}
	// Display pre order elements
	public	function preorder($node)
	{
		if ($node != null)
		{
			// Print node value
			echo "  ". $node->data;
			$this->preorder($node->left);
			$this->preorder($node->right);
		}
	}
	//  Find nth node in preorder
	public	function find_nth_preorder($node, $n)
	{
		if ($node == null)
		{
			return null;
		}
		$this->position = $this->position + 1;
		if ($n == $this->position)
		{
			//  When get Nth preorder node
			return $node;
		}
		$result = $this->find_nth_preorder($node->left, $n);
		if ($result == null)
		{
			$result = $this->find_nth_preorder($node->right, $n);
		}
		return $result;
	}
	//  Handles the request to find nth nodes in preorder traversal
	public	function find_node($n)
	{
		// Invalid node
		if ($n <= 0)
		{
			return;
		}
		else if ($this->root == null)
		{
			echo "\n Empty Tree\n";
		}
		else
		{
			$this->position = 0;
			$result = $this->find_nth_preorder($this->root, $n);
			if ($result != null)
			{
				//  Print nth node
				echo " [". $n ."-th] Preorder node is : ". $result->data ."\n";
			}
			else
			{
				echo " [". $n ."-th] Preorder node not exists \n";
			}
		}
	}
}

function main()
{
	// Create tree object
	$tree = new BinaryTree();
	/*
	  		constructor binary tree
	  		-----------------
	  		     80                            
	  		   /   \    
	  		  5     7    
	  		 / \     \               
	  		1   3     2  
	  		   / \     \
	  		  10  8     9
	  		     / \
	  		    12  4
	  		-----------------
	*/
	$tree->root = new Node(80);
	$tree->root->left = new Node(5);
	$tree->root->left->right = new Node(3);
	$tree->root->left->right->left = new Node(10);
	$tree->root->left->right->right = new Node(8);
	$tree->root->left->right->right->left = new Node(12);
	$tree->root->left->right->right->right = new Node(4);
	$tree->root->left->left = new Node(1);
	$tree->root->right = new Node(7);
	$tree->root->right->right = new Node(2);
	$tree->root->right->right->right = new Node(9);
	echo "\n Tree Nodes \n";
	$tree->preorder($tree->root);
	echo "\n";
	// Test Case
	$tree->find_node(4);
	$tree->find_node(1);
	$tree->find_node(3);
	$tree->find_node(11);
	$tree->find_node(5);
	$tree->find_node(17);
}
main();

Output

 Tree Nodes
  80  5  1  3  10  8  12  4  7  2  9
 [4-th] Preorder node is : 3
 [1-th] Preorder node is : 80
 [3-th] Preorder node is : 1
 [11-th] Preorder node is : 9
 [5-th] Preorder node is : 10
 [17-th] Preorder node not exists
/*
     Node Js Program 
     Find nth node in preorder traversal
*/
//  Binary Tree node
class Node
{
	constructor(data)
	{
		//  Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		// Set initial tree root to null
		this.root = null;
		this.position = 0;
	}
	// Display pre order elements
	preorder(node)
	{
		if (node != null)
		{
			// Print node value
			process.stdout.write("  " + node.data);
			this.preorder(node.left);
			this.preorder(node.right);
		}
	}
	//  Find nth node in preorder
	find_nth_preorder(node, n)
	{
		if (node == null)
		{
			return null;
		}
		this.position = this.position + 1;
		if (n == this.position)
		{
			//  When get Nth preorder node
			return node;
		}
		var result = this.find_nth_preorder(node.left, n);
		if (result == null)
		{
			result = this.find_nth_preorder(node.right, n);
		}
		return result;
	}
	//  Handles the request to find nth nodes in preorder traversal
	find_node(n)
	{
		// Invalid node
		if (n <= 0)
		{
			return;
		}
		else if (this.root == null)
		{
			process.stdout.write("\n Empty Tree\n");
		}
		else
		{
			this.position = 0;
			var result = this.find_nth_preorder(this.root, n);
			if (result != null)
			{
				//  Print nth node
				process.stdout.write(" [" + n + "-th] Preorder node is : " + result.data + "\n");
			}
			else
			{
				process.stdout.write(" [" + n + "-th] Preorder node not exists \n");
			}
		}
	}
}

function main()
{
	// Create tree object
	var tree = new BinaryTree();
	/*
	  		constructor binary tree
	  		-----------------
	  		     80                            
	  		   /   \    
	  		  5     7    
	  		 / \     \               
	  		1   3     2  
	  		   / \     \
	  		  10  8     9
	  		     / \
	  		    12  4
	  		-----------------
	*/
	tree.root = new Node(80);
	tree.root.left = new Node(5);
	tree.root.left.right = new Node(3);
	tree.root.left.right.left = new Node(10);
	tree.root.left.right.right = new Node(8);
	tree.root.left.right.right.left = new Node(12);
	tree.root.left.right.right.right = new Node(4);
	tree.root.left.left = new Node(1);
	tree.root.right = new Node(7);
	tree.root.right.right = new Node(2);
	tree.root.right.right.right = new Node(9);
	process.stdout.write("\n Tree Nodes \n");
	tree.preorder(tree.root);
	process.stdout.write("\n");
	// Test Case
	tree.find_node(4);
	tree.find_node(1);
	tree.find_node(3);
	tree.find_node(11);
	tree.find_node(5);
	tree.find_node(17);
}
main();

Output

 Tree Nodes
  80  5  1  3  10  8  12  4  7  2  9
 [4-th] Preorder node is : 3
 [1-th] Preorder node is : 80
 [3-th] Preorder node is : 1
 [11-th] Preorder node is : 9
 [5-th] Preorder node is : 10
 [17-th] Preorder node not exists
#     Python 3 Program 
#     Find nth node in preorder traversal

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

class BinaryTree :
	
	def __init__(self) :
		# Set initial tree root to null
		self.root = None
		self.position = 0
	
	# Display pre order elements
	def preorder(self, node) :
		if (node != None) :
			# Print node value
			print("  ", node.data, end = "")
			self.preorder(node.left)
			self.preorder(node.right)
		
	
	#  Find nth node in preorder
	def find_nth_preorder(self, node, n) :
		if (node == None) :
			return None
		
		self.position = self.position + 1
		if (n == self.position) :
			#  When get Nth preorder node
			return node
		
		result = self.find_nth_preorder(node.left, n)
		if (result == None) :
			result = self.find_nth_preorder(node.right, n)
		
		return result
	
	#  Handles the request to find nth nodes in preorder traversal
	def find_node(self, n) :
		if (n <= 0) :
			# Invalid node
			return
		
		elif(self.root == None) :
			print("\n Empty Tree\n", end = "")
		else :
			self.position = 0
			result = self.find_nth_preorder(self.root, n)
			if (result != None) :
				#  Print nth node
				print(" [", n ,"-th] Preorder node is : ", result.data ,"\n", end = "")
			else :
				print(" [", n ,"-th] Preorder node not exists \n", end = "")
			
		
	

def main() :
	# Create tree object
	tree = BinaryTree()
	# 
	# 		constructor binary tree
	# 		-----------------
	# 		     80                            
	# 		   /   \    
	# 		  5     7    
	# 		 / \     \               
	# 		1   3     2  
	# 		   / \     \
	# 		  10  8     9
	# 		     / \
	# 		    12  4
	# 		-----------------
	# 		
	
	tree.root = Node(80)
	tree.root.left = Node(5)
	tree.root.left.right = Node(3)
	tree.root.left.right.left = Node(10)
	tree.root.left.right.right = Node(8)
	tree.root.left.right.right.left = Node(12)
	tree.root.left.right.right.right = Node(4)
	tree.root.left.left = Node(1)
	tree.root.right = Node(7)
	tree.root.right.right = Node(2)
	tree.root.right.right.right = Node(9)
	print("\n Tree Nodes \n", end = "")
	tree.preorder(tree.root)
	print("\n", end = "")
	# Test Case
	tree.find_node(4)
	tree.find_node(1)
	tree.find_node(3)
	tree.find_node(11)
	tree.find_node(5)
	tree.find_node(17)

if __name__ == "__main__": main()

Output

 Tree Nodes
   80   5   1   3   10   8   12   4   7   2   9
 [ 4 -th] Preorder node is :  3
 [ 1 -th] Preorder node is :  80
 [ 3 -th] Preorder node is :  1
 [ 11 -th] Preorder node is :  9
 [ 5 -th] Preorder node is :  10
 [ 17 -th] Preorder node not exists
#     Ruby Program 
#     Find nth node in preorder traversal

#  Binary Tree node
class Node  
	# Define the accessor and reader of class Node  
	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, :position
	attr_accessor :root, :position
 
	
	def initialize() 
		# Set initial tree root to null
		self.root = nil
		self.position = 0
	end

	# Display pre order elements
	def preorder(node) 
		if (node != nil) 
			# Print node value
			print("  ", node.data)
			self.preorder(node.left)
			self.preorder(node.right)
		end

	end

	#  Find nth node in preorder
	def find_nth_preorder(node, n) 
		if (node == nil) 
			return nil
		end

		self.position = self.position + 1
		if (n == self.position) 
			#  When get Nth preorder node
			return node
		end

		result = self.find_nth_preorder(node.left, n)
		if (result == nil) 
			result = self.find_nth_preorder(node.right, n)
		end

		return result
	end

	#  Handles the request to find nth nodes in preorder traversal
	def find_node(n) 
		if (n <= 0) 
			# Invalid node
			return
		elsif(self.root == nil) 
			print("\n Empty Tree\n")
		else 
			self.position = 0
			result = self.find_nth_preorder(self.root, n)
			if (result != nil) 
				#  Print nth node
				print(" [", n ,"-th] Preorder node is : ", result.data ,"\n")
			else 
				print(" [", n ,"-th] Preorder node not exists \n")
			end

		end

	end

end

def main() 
	# Create tree object
	tree = BinaryTree.new()
	# 
	# 		constructor binary tree
	# 		-----------------
	# 		     80                            
	# 		   /   \    
	# 		  5     7    
	# 		 / \     \               
	# 		1   3     2  
	# 		   / \     \
	# 		  10  8     9
	# 		     / \
	# 		    12  4
	# 		-----------------
	# 		
	
	tree.root = Node.new(80)
	tree.root.left = Node.new(5)
	tree.root.left.right = Node.new(3)
	tree.root.left.right.left = Node.new(10)
	tree.root.left.right.right = Node.new(8)
	tree.root.left.right.right.left = Node.new(12)
	tree.root.left.right.right.right = Node.new(4)
	tree.root.left.left = Node.new(1)
	tree.root.right = Node.new(7)
	tree.root.right.right = Node.new(2)
	tree.root.right.right.right = Node.new(9)
	print("\n Tree Nodes \n")
	tree.preorder(tree.root)
	print("\n")
	# Test Case
	tree.find_node(4)
	tree.find_node(1)
	tree.find_node(3)
	tree.find_node(11)
	tree.find_node(5)
	tree.find_node(17)
end

main()

Output

 Tree Nodes 
  80  5  1  3  10  8  12  4  7  2  9
 [4-th] Preorder node is : 3
 [1-th] Preorder node is : 80
 [3-th] Preorder node is : 1
 [11-th] Preorder node is : 9
 [5-th] Preorder node is : 10
 [17-th] Preorder node not exists 

/*
     Scala Program 
     Find nth node in preorder traversal
*/
//  Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class BinaryTree(var root: Node , var position: Int)
{
	def this()
	{
		this(null, 0);
	}
	// Display pre order elements
	def preorder(node: Node): Unit = {
		if (node != null)
		{
			// Print node value
			print("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	//  Find nth node in preorder
	def find_nth_preorder(node: Node, n: Int): Node = {
		if (node == null)
		{
			return null;
		}
		this.position = this.position + 1;
		if (n == this.position)
		{
			//  When get Nth preorder node
			return node;
		}
		var result: Node = find_nth_preorder(node.left, n);
		if (result == null)
		{
			result = find_nth_preorder(node.right, n);
		}
		return result;
	}
	//  Handles the request to find nth nodes in preorder traversal
	def find_node(n: Int): Unit = {
		// Invalid node
		if (n <= 0)
		{
			return;
		}
		else if (this.root == null)
		{
			print("\n Empty Tree\n");
		}
		else
		{
			this.position = 0;
			var result: Node = find_nth_preorder(this.root, n);
			if (result != null)
			{
				//  Print nth node
				print(" [" + n + "-th] Preorder node is : " + result.data + "\n");
			}
			else
			{
				print(" [" + n + "-th] Preorder node not exists \n");
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create tree object
		var tree: BinaryTree = new BinaryTree();
		/*
		  		constructor binary tree
		  		-----------------
		  		     80                            
		  		   /   \    
		  		  5     7    
		  		 / \     \               
		  		1   3     2  
		  		   / \     \
		  		  10  8     9
		  		     / \
		  		    12  4
		  		-----------------
		*/
		tree.root = new Node(80);
		tree.root.left = new Node(5);
		tree.root.left.right = new Node(3);
		tree.root.left.right.left = new Node(10);
		tree.root.left.right.right = new Node(8);
		tree.root.left.right.right.left = new Node(12);
		tree.root.left.right.right.right = new Node(4);
		tree.root.left.left = new Node(1);
		tree.root.right = new Node(7);
		tree.root.right.right = new Node(2);
		tree.root.right.right.right = new Node(9);
		print("\n Tree Nodes \n");
		tree.preorder(tree.root);
		print("\n");
		// Test Case
		tree.find_node(4);
		tree.find_node(1);
		tree.find_node(3);
		tree.find_node(11);
		tree.find_node(5);
		tree.find_node(17);
	}
}

Output

 Tree Nodes
  80  5  1  3  10  8  12  4  7  2  9
 [4-th] Preorder node is : 3
 [1-th] Preorder node is : 80
 [3-th] Preorder node is : 1
 [11-th] Preorder node is : 9
 [5-th] Preorder node is : 10
 [17-th] Preorder node not exists
/*
     Swift 4 Program 
     Find nth node in preorder traversal
*/
//  Binary Tree node
class Node
{
	var data: Int;
	var left: Node? ;
	var right: Node? ;
	init(_ data: Int)
	{
		//  Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinaryTree
{
	var root: Node? ;
	var position: Int;
	init()
	{
		// Set initial tree root to null
		self.root = nil;
		self.position = 0;
	}
	// Display pre order elements
	func preorder(_ node: Node? )
	{
		if (node != nil)
		{
			// Print node value
			print("  ", node!.data, terminator: "");
			self.preorder(node!.left);
			self.preorder(node!.right);
		}
	}
	//  Find nth node in preorder
	func find_nth_preorder(_ node: Node? , _ n : Int)->Node?
	{
		if (node == nil)
		{
			return nil;
		}
		self.position = self.position + 1;
		if (n == self.position)
		{
			//  When get Nth preorder node
			return node;
		}
		var result: Node? = self.find_nth_preorder(node!.left, n);
		if (result == nil)
		{
			result = self.find_nth_preorder(node!.right, n);
		}
		return result;
	}
	//  Handles the request to find nth nodes in preorder traversal
	func find_node(_ n: Int)
	{
		// Invalid node
		if (n <= 0)
		{
			return;
		}
		else if (self.root == nil)
		{
			print("\n Empty Tree\n", terminator: "");
		}
		else
		{
			self.position = 0;
			let result: Node? = self.find_nth_preorder(self.root, n);
			if (result != nil)
			{
				//  Print nth node
				print(" [", n ,"-th]Preorder node is : ", result!.data ,"\n", terminator: "");
			}
			else
			{
				print(" [", n ,"-th]Preorder node not exists \n", terminator: "");
			}
		}
	}
}
func main()
{
	// Create tree object
	let tree: BinaryTree = BinaryTree();
	/*
  		constructor binary tree
  		-----------------
  		     80                            
  		   /   \    
  		  5     7    
  		 / \     \               
  		1   3     2  
  		   / \     \
  		  10  8     9
  		     / \
  		    12  4
  		-----------------
	*/
	tree.root = Node(80);
	tree.root!.left = Node(5);
	tree.root!.left!.right = Node(3);
	tree.root!.left!.right!.left = Node(10);
	tree.root!.left!.right!.right = Node(8);
	tree.root!.left!.right!.right!.left = Node(12);
	tree.root!.left!.right!.right!.right = Node(4);
	tree.root!.left!.left = Node(1);
	tree.root!.right = Node(7);
	tree.root!.right!.right = Node(2);
	tree.root!.right!.right!.right = Node(9);
	print("\n Tree Nodes");
	tree.preorder(tree.root);
	print("\n", terminator: "");
	// Test Case
	tree.find_node(4);
	tree.find_node(1);
	tree.find_node(3);
	tree.find_node(11);
	tree.find_node(5);
	tree.find_node(17);
}
main();

Output

 Tree Nodes
   80   5   1   3   10   8   12   4   7   2   9
 [ 4 -th]Preorder node is :  3
 [ 1 -th]Preorder node is :  80
 [ 3 -th]Preorder node is :  1
 [ 11 -th]Preorder node is :  9
 [ 5 -th]Preorder node is :  10
 [ 17 -th]Preorder node not exists
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