# 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``````

## 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

© 2022, kalkicode.com, All rights reserved