Find n-th node of inorder traversal in binary tree

Inorder traversal of a binary tree and find out the n-th node.

Find n-th node of inorder traversal

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







© 2021, kalkicode.com, All rights reserved