Find n-th node of inorder traversal in binary tree
Inorder traversal of a binary tree and find out the n-th node.
Here given code implementation process.
/*
C Program
+ Find n-th node of inorder traversal in binary tree
*/
#include<stdio.h>
#include<stdlib.h>
//structure of Binary Tree node
struct Node{
int data;
struct Node*left,*right;
};
//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes
struct Node* insert(int data){
//create dynamic memory to new binary tree 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; //Initially node left-pointer is NULL
new_node->right=NULL;//Initially node right-pointer is NULL
}else{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
//return reference
return new_node;
}
//Check nth inorder node
void nth_inorder(struct Node*node,int *position){
if(node!=NULL && *position!=0){
nth_inorder(node->left,position);
*position-=1;
if(*position==0){
printf(" Data %d\n", node->data);
}
nth_inorder(node->right,position);
}
}
int main(){
struct Node*root=NULL;
int position=4;
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
\
7
Inorder : 4 7 2 1 5 3 6
*/
//Insertion of binary tree nodes
root =insert(1);
root->left =insert(2);
root->right =insert(3);
root->right->right =insert(6);
root->right->left =insert(5);
root->left->left =insert(4);
root->left->left->right =insert(7);
//Check Leaf Level
printf("\n Position %d : ",position);
nth_inorder(root,&position);
position=6;
printf("\n Position %d : ",position);
nth_inorder(root,&position);
return 0;
}Output
Position 4 : Data 1
Position 6 : Data 3/*
C++ Program
+ Find n-th node of inorder traversal in binary tree
*/
#include<iostream>
using namespace std;
//Structure of Binary Tree node
class Node{
public:
int data;
Node*left,*right;
//make a tree node
Node(int data){
//assign field values
this->data=data;
left=right=NULL;
}
};
class BinaryTree{
public:
Node*root;
BinaryTree();
void nth_inorder(Node*,int*);
};
//set initial tree root to NULL
BinaryTree:: BinaryTree(){
root=NULL;
}
//Check nth inorder node
void BinaryTree:: nth_inorder(Node*node,int *position){
if(node!=NULL && *position!=0){
nth_inorder(node->left,position);
*position-=1;
if(*position==0){
cout<<" Data "<< node->data<<endl;
}
nth_inorder(node->right,position);
}
}
int main(){
BinaryTree obj;
int position=4;
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
\
7
*/
//insertion of binary Tree nodes
obj.root =new Node(1);
obj.root->left =new Node(2);
obj.root->right =new Node(3);
obj.root->right->right =new Node(6);
obj.root->right->left =new Node(5);
obj.root->left->left =new Node(4);
obj.root->left->left->right =new Node(7);
//Check Leaf Level
cout<<" Position "<<position <<" : ";
obj.nth_inorder(obj.root,&position);
position=6;
cout<<" Position "<< position <<" : ";
obj.nth_inorder(obj.root,&position);
return 0;
}Output
Position 4 : Data 1
Position 6 : Data 3/*
Java Program
Find n-th node of inorder traversal in binary tree
*/
//Class of Binary Tree node
class Node{
int data;
Node left, right;
//make a tree node
public Node(int data){
//assign field values
this.data=data;
left=right=null;
}
};
class BinaryTree{
public Node root;
public int position;
public BinaryTree(){
//set initial tree root to null
root=null;
position=0;
}
//Check Leaf nodes are at same level
public void nthInorder(Node node){
if(node!=null && position!=0){
nthInorder(node.left);
position-=1;
if(position==0){
System.out.println(" Data "+node.data);
}
nthInorder(node.right);
}
}
public static void main(String[] args){
//Make object of Binary Tree
BinaryTree obj=new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
\
7
Inorder : 4 7 2 1 5 3 6
*/
//insertion of binary Tree nodes
obj.root =new Node(1);
obj.root.left =new Node(2);
obj.root.right =new Node(3);
obj.root.right.right =new Node(6);
obj.root.right.left =new Node(5);
obj.root.left.left =new Node(4);
obj.root.left.left.right =new Node(7);
obj.position=4;
System.out.print(" Position : "+obj.position);
obj.nthInorder(obj.root);
obj.position=6;
System.out.print(" Position : "+obj.position);
obj.nthInorder(obj.root);
}
}Output
Position : 4 Data 1
Position : 6 Data 3
#Python Program
#Find n-th node of inorder traversal in binary tree
#using recursion
class Node:
def __init__(self,data):
#Assign node value
self.data=data
self.left,self.right=None,None
class BinaryTree:
def __init__(self):
#set initial tree root to None
self.root=None
self.position=0
#Display tree element inorder form
def inorder(self,node):
if(node!=None):
self.inorder(node.left)
#Print node value
print(node.data,end=" ")
self.inorder(node.right)
#Check Leaf nodes are at same level
def nthInorder(self,node):
if(node!=None and self.position!=0):
self.nthInorder(node.left)
self.position-=1
if(self.position==0):
print(" Data ",node.data)
self.nthInorder(node.right)
def main():
#Make object of Binary Tree
obj=BinaryTree()
# Make A Binary Tree
#-----------------------
# 1
# / \
# 2 3
# / / \
# 4 5 6
# \
# 7
#insertion of binary Tree nodes
obj.root = Node(1)
obj.root.left = Node(2)
obj.root.right = Node(3)
obj.root.right.right = Node(6)
obj.root.right.left = Node(5)
obj.root.left.left = Node(4)
obj.root.left.left.right = Node(7)
obj.position=4
print(" Position : ",obj.position)
obj.nthInorder(obj.root)
obj.position=6
print(" Position : ",obj.position)
obj.nthInorder(obj.root)
if __name__=="__main__":
main()Output
Position : 4
Data 1
Position : 6
Data 3/*
C# Program
Find n-th node of inorder traversal in binary tree
//using recursion
*/
using System;
class Node{
public int data;
public Node left, right;
//Make a tree node
public Node(int data){
//Assign fields values
this.data=data;
left=right=null;
}
};
class BinaryTree
{
public Node root;
public int position;
public BinaryTree(){
//set initial tree root to null
root = null;
position = 0;
}
//Check Leaf nodes are at same level
public void nthInorder(Node node){
if(node!=null && position!=0){
nthInorder(node.left);
position-=1;
if(position==0){
Console.WriteLine(" Data "+node.data);
}
nthInorder(node.right);
}
}
static void Main()
{
//Make object of Binary Tree
BinaryTree obj=new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
\
7
Inorder : 4 7 2 1 5 3 6
*/
//insertion of binary Tree nodes
obj.root =new Node(1);
obj.root.left =new Node(2);
obj.root.right =new Node(3);
obj.root.right.right =new Node(6);
obj.root.right.left =new Node(5);
obj.root.left.left =new Node(4);
obj.root.left.left.right =new Node(7);
obj.position=4;
Console.WriteLine(" Position : {0}",obj.position);
obj.nthInorder(obj.root);
obj.position=6;
Console.WriteLine(" Position : {0}",obj.position);
obj.nthInorder(obj.root);
}
}Output
Position : 4
Data 1
Position : 6
Data 3
<?php
//Php program
//Find n-th node of inorder traversal in binary tree
//using recursion
class Node
{
public $data;
public $left;
public $right;
function __construct($data)
{
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
class BinaryTree{
public $root;
function __construct()
{
//set initial tree root to null
$this->root=NULL;
}
//Check nth inorder node
public function nth_inorder($node,&$position){
if($node!=NULL && $position!=0){
$this->nth_inorder($node->left,$position);
$position-=1;
if($position==0){
echo " Data ". $node->data."\n";
}
$this->nth_inorder($node->right,$position);
}
}
}
function main(){
//Make object of Binary Tree
$obj=new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
\
7
*/
//insertion of binary Tree nodes
$obj->root = new Node(1);
$obj->root->left = new Node(2);
$obj->root->right = new Node(3);
$obj->root->right->right = new Node(6);
$obj->root->right->left = new Node(5);
$obj->root->left->left = new Node(4);
$obj->root->left->left->right = new Node(7);
$position=4;
echo ("\n Position : ".$position);
$obj->nth_inorder($obj->root,$position);
$position=6;
echo ("\n Position : ".$position);
$obj->nth_inorder($obj->root,$position);
}
main();
?>
Output
Position : 4 Data 1
Position : 6 Data 3
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