Inorder traversal between two binary tree nodes

Here given code implementation process.

// C program for
// Inorder traversal between two binary tree nodes
#include <stdio.h>
#include <stdlib.h>

// Tree Node
struct TreeNode
{
	int data;
	struct TreeNode *left;
	struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
	struct TreeNode *root;
};
// Create new tree
struct BinaryTree *newTree()
{
	// Create a dynamic tree 
	struct BinaryTree *tree = 
      (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
	if (tree != NULL)
	{
		tree->root = NULL;
	}
	else
	{
		printf("Memory Overflow to Create tree Tree\n");
	}
	// return new tree
	return tree;
}
// This is creates and returns the new binary tree node
struct TreeNode *getNode(int data)
{
	// Create dynamic node
	struct TreeNode *node = 
      (struct TreeNode *) malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		// Set data and pointer values
		node->data = data;
		node->left = NULL;
		node->right = NULL;
	}
	else
	{
		// This is indicates, segmentation fault 
      	// or memory overflow problem
		printf("Memory Overflow\n");
	}
	// return new node
	return node;
}
// inorder traversal of binary tree
void inOrder(struct TreeNode *node)
{
	if (node != NULL)
	{
		// Visit left subtree
		inOrder(node->left);
		// Print node value
		printf("  %d", node->data);
		// Visit right subtree
		inOrder(node->right);
	}
}
void betweenInorder(struct TreeNode *node, 
                    int *status, int n1, int n2, int flag[])
{
	if (node != NULL)
	{
		// Visit left subtree
		betweenInorder(node->left, status, n1, n2, flag);
		if (n1 == node->data && flag[0] == 0)
		{
			// We get first node n1
			flag[0] = 1;
		}
		else if (n2 == node->data && flag[1] == 0)
		{
			// We get second node n2
			flag[1] = 1;
		}
		else if (flag[0] != flag[1])
		{
			*status = 1;
			// Print intermediate inorder nodes
			printf("  %d", node->data);
		}
		// Visit right subtree
		betweenInorder(node->right, status, n1, n2, flag);
	}
}
// Check that given key exists in binary tree
int findNode(struct TreeNode *node, int key)
{
	if (node == NULL)
	{
		return 0;
	}
	else if (node->data == key)
	{
		// Found the key node then return 1 indicates node exists
		return 1;
	}
	else if (findNode(node->left, key) == 1 || 
             findNode(node->right, key) == 1)
	{
		return 1;
	}
	return 0;
}
// This function are use to detect given node 
// n1 and n2 exist or not in binary tree if node exist
void nodeInorder(struct TreeNode *node, int n1, int n2)
{
	if (node == NULL)
	{
		// When tree is empty
		return;
	}
	if (findNode(node, n1) == 1 && findNode(node, n2) == 1)
	{
		// When both node exists
		// flag are used to indicate node status
		int flag[2] = {
			0 , 0
		};
		int status = 0;
		// Display node value
		printf("\n Inorder between (%d %d) is\n ", n1, n2);
		// Inorder between n1 and n2
		betweenInorder(node, & status, n1, n2, flag);
		if (status == 0)
		{
			printf(" None \n");
		}
	}
	else
	{
		printf(" \n Given node pair (%d,%d) are not exist ", n1, n2);
	}
}
int main(int argc, char
	const *argv[])
{
	struct BinaryTree *tree = newTree();
	/*
	         4                            
	       /   \    
	      12    7    
	     / \      \               
	    2   3      1
	       / \    / 
	      6   8  5
	     /     \  
	    9       10    
	-----------------
	  Constructing binary tree

	*/
	tree->root = getNode(4);
	tree->root->left = getNode(12);
	tree->root->left->right = getNode(3);
	tree->root->left->right->left = getNode(6);
	tree->root->left->right->left->left = getNode(9);
	tree->root->left->right->right = getNode(8);
	tree->root->left->right->right->right = getNode(10);
	tree->root->left->left = getNode(2);
	tree->root->right = getNode(7);
	tree->root->right->right = getNode(1);
	tree->root->right->right->left = getNode(5);
	inOrder(tree->root);
	// Test cases
	nodeInorder(tree->root, 2, 10);
	nodeInorder(tree->root, 8, 5);
	nodeInorder(tree->root, 1, 6);
	nodeInorder(tree->root, 3, 6);
  	nodeInorder(tree->root, 3, 11);
	return 0;
}

input

  2  12  9  6  3  8  10  4  7  5  1
 Inorder between (2 10) is
   12  9  6  3  8
 Inorder between (8 5) is
   10  4  7
 Inorder between (1 6) is
   3  8  10  4  7  5
 Inorder between (3 6) is
  None

 Given node pair (3,11) are not exist
/*
    Java Program
    Inorder traversal between two binary tree nodes
*/
// Binary Tree node
class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public boolean status;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
		this.status = false;
	}
	// inorder traversal of binary tree
	public void inOrder(TreeNode node)
	{
		if (node != null)
		{
			// Visit left subtree
			inOrder(node.left);
			// Print node value
			System.out.print(" " + node.data);
			// Visit right subtree
			inOrder(node.right);
		}
	}
	public void betweenInorder(TreeNode node, 
                                int n1, int n2, boolean[] flag)
	{
		if (node != null)
		{
			// Visit left subtree
			betweenInorder(node.left, n1, n2, flag);
			if (n1 == node.data && flag[0] == false)
			{
				// We get first node n1
				flag[0] = true;
			}
			else if (n2 == node.data && flag[1] == false)
			{
				// We get second node n2
				flag[1] = true;
			}
			else if (flag[0] != flag[1])
			{
				this.status = true;
				// Print intermediate inorder nodes
				System.out.print(" " + node.data);
			}
			// Visit right subtree
			betweenInorder(node.right, n1, n2, flag);
		}
	}
	// Check that given key exists in binary tree
	public boolean findNode(TreeNode node, int key)
	{
		if (node == null)
		{
			return false;
		}
		else if (node.data == key)
		{
			// Found the key node then return 1 indicates node exists
			return true;
		}
		else if (findNode(node.left, key) || 
                 findNode(node.right, key))
		{
			return true;
		}
		return false;
	}
	// This function are use to detect given node
	// n1 and n2 exist or not in binary tree if node exist
	public void nodeInorder(int n1, int n2)
	{
		if (this.root == null)
		{
			// When tree is empty
			return;
		}
		if (findNode(this.root, n1)  && 
            findNode(this.root, n2))
		{
			// When both node exists
			// flag are used to indicate node status
			boolean[] flag = {
				false , false
			};
			this.status = false;
			// Display node value
			System.out.print("\n Inorder between (" + 
                             n1 + " " + n2 + ") is\n ");
			// Inorder between n1 and n2
			betweenInorder(this.root, n1, n2, flag);
			if (this.status == false)
			{
				System.out.print(" None \n");
			}
		}
		else
		{
			System.out.print(" \n Given node pair (" + 
                             n1 + "," + n2 + ") are not exist ");
		}
	}
	public static void main(String[] args)
	{
		// Create new binary tree
		BinaryTree tree = new BinaryTree();
		/*
		         4                            
		       /   \    
		      12    7    
		     / \      \               
		    2   3      1
		       / \    / 
		      6   8  5
		     /     \  
		    9       10    
		-----------------
		  Constructing binary tree
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(12);
		tree.root.left.right = new TreeNode(3);
		tree.root.left.right.left = new TreeNode(6);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.right.right.right = new TreeNode(10);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(7);
		tree.root.right.right = new TreeNode(1);
		tree.root.right.right.left = new TreeNode(5);
		tree.inOrder(tree.root);
		// Test cases
		tree.nodeInorder(2, 10);
		tree.nodeInorder(8, 5);
		tree.nodeInorder(1, 6);
		tree.nodeInorder(3, 6);
		tree.nodeInorder(3, 11);
	}
}

input

 2 12 9 6 3 8 10 4 7 5 1
 Inorder between (2 10) is
  12 9 6 3 8
 Inorder between (8 5) is
  10 4 7
 Inorder between (1 6) is
  3 8 10 4 7 5
 Inorder between (3 6) is
  None

 Given node pair (3,11) are not exist
// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program
    Inorder traversal between two binary tree nodes
*/

// Binary Tree node
class TreeNode
{
	public: 
    int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		// Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinaryTree
{
	public: 
    TreeNode *root;
	bool status;
	BinaryTree()
	{
		this->root = NULL;
		this->status = false;
	}
	// inorder traversal of binary tree
	void inOrder(TreeNode *node)
	{
		if (node != NULL)
		{
			// Visit left subtree
			this->inOrder(node->left);
			// Print node value
			cout << " " << node->data;
			// Visit right subtree
			this->inOrder(node->right);
		}
	}
	void betweenInorder(TreeNode *node, 
                        int n1, int n2, bool flag[])
	{
		if (node != NULL)
		{
			// Visit left subtree
			this->betweenInorder(node->left, n1, n2, flag);
			if (n1 == node->data && flag[0] == false)
			{
				// We get first node n1
				flag[0] = true;
			}
			else if (n2 == node->data && flag[1] == false)
			{
				// We get second node n2
				flag[1] = true;
			}
			else if (flag[0] != flag[1])
			{
				this->status = true;
				// Print intermediate inorder nodes
				cout << " " << node->data;
			}
			// Visit right subtree
			this->betweenInorder(node->right, n1, n2, flag);
		}
	}
	// Check that given key exists in binary tree
	bool findNode(TreeNode *node, int key)
	{
		if (node == NULL)
		{
			return false;
		}
		else if (node->data == key)
		{
			// Found the key node then return 1 indicates node exists
			return true;
		}
		else if (this->findNode(node->left, key) 
                 || this->findNode(node->right, key))
		{
			return true;
		}
		return false;
	}
	// This function are use to detect given node
	// n1 and n2 exist or not in binary tree if node exist
	void nodeInorder(int n1, int n2)
	{
		if (this->root == NULL)
		{
			// When tree is empty
			return;
		}
		if (this->findNode(this->root, n1) 
            && this->findNode(this->root, n2))
		{
			// When both node exists
			// flag are used to indicate node status
			bool flag[] = {
				false , false
			};
			this->status = false;
			// Display node value
			cout << "\n Inorder between (" 
          		 << n1 << " " << n2 << ") is\n ";
			// Inorder between n1 and n2
			this->betweenInorder(this->root, n1, n2, flag);
			if (this->status == false)
			{
				cout << " None \n";
			}
		}
		else
		{
			cout << " \n Given node pair (" << n1 
          		 << "," << n2 << ") are not exist ";
		}
	}
};
int main()
{
	// Create new binary tree
	BinaryTree *tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	      12    7    
	     / \      \               
	    2   3      1
	       / \    / 
	      6   8  5
	     /     \  
	    9       10    
	-----------------
	  Constructing binary tree
	*/
	tree->root = new TreeNode(4);
	tree->root->left = new TreeNode(12);
	tree->root->left->right = new TreeNode(3);
	tree->root->left->right->left = new TreeNode(6);
	tree->root->left->right->left->left = new TreeNode(9);
	tree->root->left->right->right = new TreeNode(8);
	tree->root->left->right->right->right = new TreeNode(10);
	tree->root->left->left = new TreeNode(2);
	tree->root->right = new TreeNode(7);
	tree->root->right->right = new TreeNode(1);
	tree->root->right->right->left = new TreeNode(5);
	tree->inOrder(tree->root);
	// Test cases
	tree->nodeInorder(2, 10);
	tree->nodeInorder(8, 5);
	tree->nodeInorder(1, 6);
	tree->nodeInorder(3, 6);
	tree->nodeInorder(3, 11);
	return 0;
}

input

 2 12 9 6 3 8 10 4 7 5 1
 Inorder between (2 10) is
  12 9 6 3 8
 Inorder between (8 5) is
  10 4 7
 Inorder between (1 6) is
  3 8 10 4 7 5
 Inorder between (3 6) is
  None

 Given node pair (3,11) are not exist
// Include namespace system
using System;
/*
    Csharp Program
    Inorder traversal between two binary tree nodes
*/
// Binary Tree node
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public Boolean status;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
		this.status = false;
	}
	// inorder traversal of binary tree
	public void inOrder(TreeNode node)
	{
		if (node != null)
		{
			// Visit left subtree
			this.inOrder(node.left);
			// Print node value
			Console.Write(" " + node.data);
			// Visit right subtree
			this.inOrder(node.right);
		}
	}
	public void betweenInorder(TreeNode node, 
                                int n1, int n2, Boolean[] flag)
	{
		if (node != null)
		{
			// Visit left subtree
			this.betweenInorder(node.left, n1, n2, flag);
			if (n1 == node.data && flag[0] == false)
			{
				// We get first node n1
				flag[0] = true;
			}
			else if (n2 == node.data && flag[1] == false)
			{
				// We get second node n2
				flag[1] = true;
			}
			else if (flag[0] != flag[1])
			{
				this.status = true;
				// Print intermediate inorder nodes
				Console.Write(" " + node.data);
			}
			// Visit right subtree
			this.betweenInorder(node.right, n1, n2, flag);
		}
	}
	// Check that given key exists in binary tree
	public Boolean findNode(TreeNode node, int key)
	{
		if (node == null)
		{
			return false;
		}
		else if (node.data == key)
		{
			// Found the key node then return 1 indicates node exists
			return true;
		}
		else if (this.findNode(node.left, key) 
                 || this.findNode(node.right, key))
		{
			return true;
		}
		return false;
	}
	// This function are use to detect given node
	// n1 and n2 exist or not in binary tree if node exist
	public void nodeInorder(int n1, int n2)
	{
		if (this.root == null)
		{
			// When tree is empty
			return;
		}
		if (this.findNode(this.root, n1) 
            && this.findNode(this.root, n2))
		{
			// When both node exists
			// flag are used to indicate node status
			Boolean[] flag = {
				false , false
			};
			this.status = false;
			// Display node value
			Console.Write("\n Inorder between (" + n1 + " " + n2 + ") is\n ");
			// Inorder between n1 and n2
			this.betweenInorder(this.root, n1, n2, flag);
			if (this.status == false)
			{
				Console.Write(" None \n");
			}
		}
		else
		{
			Console.Write(" \n Given node pair (" + n1 + "," + n2 + ") are not exist ");
		}
	}
	public static void Main(String[] args)
	{
		// Create new binary tree
		BinaryTree tree = new BinaryTree();
		/*
		         4                            
		       /   \    
		      12    7    
		     / \      \               
		    2   3      1
		       / \    / 
		      6   8  5
		     /     \  
		    9       10    
		-----------------
		  Constructing binary tree
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(12);
		tree.root.left.right = new TreeNode(3);
		tree.root.left.right.left = new TreeNode(6);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.right.right.right = new TreeNode(10);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(7);
		tree.root.right.right = new TreeNode(1);
		tree.root.right.right.left = new TreeNode(5);
		tree.inOrder(tree.root);
		// Test cases
		tree.nodeInorder(2, 10);
		tree.nodeInorder(8, 5);
		tree.nodeInorder(1, 6);
		tree.nodeInorder(3, 6);
		tree.nodeInorder(3, 11);
	}
}

input

 2 12 9 6 3 8 10 4 7 5 1
 Inorder between (2 10) is
  12 9 6 3 8
 Inorder between (8 5) is
  10 4 7
 Inorder between (1 6) is
  3 8 10 4 7 5
 Inorder between (3 6) is
  None

 Given node pair (3,11) are not exist
<?php
/*
    Php Program
    Inorder traversal between two binary tree nodes
*/
// Binary Tree node
class TreeNode
{
	public $data;
	public $left;
	public $right;
	public	function __construct($data)
	{
		// Set node value
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class BinaryTree
{
	public $root;
	public $status;
	public	function __construct()
	{
		$this->root = NULL;
		$this->status = false;
	}
	// inorder traversal of binary tree
	public	function inOrder($node)
	{
		if ($node != NULL)
		{
			// Visit left subtree
			$this->inOrder($node->left);
			// Print node value
			echo(" ".$node->data);
			// Visit right subtree
			$this->inOrder($node->right);
		}
	}
	public	function betweenInorder($node, $n1, $n2, &$flag)
	{
		if ($node != NULL)
		{
			// Visit left subtree
			$this->betweenInorder($node->left, $n1, $n2, $flag);
			if ($n1 == $node->data && $flag[0] == false)
			{
				// We get first node n1
				$flag[0] = true;
			}
			else if ($n2 == $node->data && $flag[1] == false)
			{
				// We get second node n2
				$flag[1] = true;
			}
			else if ($flag[0] != $flag[1])
			{
				$this->status = true;
				// Print intermediate inorder nodes
				echo(" ".$node->data);
			}
			// Visit right subtree
			$this->betweenInorder($node->right, $n1, $n2, $flag);
		}
	}
	// Check that given key exists in binary tree
	public	function findNode($node, $key)
	{
		if ($node == NULL)
		{
			return false;
		}
		else if ($node->data == $key)
		{
			// Found the key node then return 1 indicates node exists
			return true;
		}
		else if ($this->findNode($node->left, $key) 
                 || $this->findNode($node->right, $key))
		{
			return true;
		}
		return false;
	}
	// This function are use to detect given node
	// n1 and n2 exist or not in binary tree if node exist
	public	function nodeInorder($n1, $n2)
	{
		if ($this->root == NULL)
		{
			// When tree is empty
			return;
		}
		if ($this->findNode($this->root, $n1) 
            && $this->findNode($this->root, $n2))
		{
			// When both node exists
			// flag are used to indicate node status
			$flag = array(false, false);
			$this->status = false;
			// Display node value
			echo("\n Inorder between (".$n1.
				" ".$n2.
				") is\n ");
			// Inorder between n1 and n2
			$this->betweenInorder($this->root, $n1, $n2, $flag);
			if ($this->status == false)
			{
				echo(" None \n");
			}
		}
		else
		{
			echo(" \n Given node pair (".$n1.
				",".$n2.
				") are not exist ");
		}
	}
}

function main()
{
	// Create new binary tree
	$tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	      12    7    
	     / \      \               
	    2   3      1
	       / \    / 
	      6   8  5
	     /     \  
	    9       10    
	-----------------
	  Constructing binary tree
	*/
	$tree->root = new TreeNode(4);
	$tree->root->left = new TreeNode(12);
	$tree->root->left->right = new TreeNode(3);
	$tree->root->left->right->left = new TreeNode(6);
	$tree->root->left->right->left->left = new TreeNode(9);
	$tree->root->left->right->right = new TreeNode(8);
	$tree->root->left->right->right->right = new TreeNode(10);
	$tree->root->left->left = new TreeNode(2);
	$tree->root->right = new TreeNode(7);
	$tree->root->right->right = new TreeNode(1);
	$tree->root->right->right->left = new TreeNode(5);
	$tree->inOrder($tree->root);
	// Test cases
	$tree->nodeInorder(2, 10);
	$tree->nodeInorder(8, 5);
	$tree->nodeInorder(1, 6);
	$tree->nodeInorder(3, 6);
	$tree->nodeInorder(3, 11);
}
main();

input

 2 12 9 6 3 8 10 4 7 5 1
 Inorder between (2 10) is
  12 9 6 3 8
 Inorder between (8 5) is
  10 4 7
 Inorder between (1 6) is
  3 8 10 4 7 5
 Inorder between (3 6) is
  None

 Given node pair (3,11) are not exist
/*
    Node JS Program
    Inorder traversal between two binary tree nodes
*/
// Binary Tree node
class TreeNode
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
		this.status = false;
	}
	// inorder traversal of binary tree
	inOrder(node)
	{
		if (node != null)
		{
			// Visit left subtree
			this.inOrder(node.left);
			// Print node value
			process.stdout.write(" " + node.data);
			// Visit right subtree
			this.inOrder(node.right);
		}
	}
	betweenInorder(node, n1, n2, flag)
	{
		if (node != null)
		{
			// Visit left subtree
			this.betweenInorder(node.left, n1, n2, flag);
			if (n1 == node.data && flag[0] == false)
			{
				// We get first node n1
				flag[0] = true;
			}
			else if (n2 == node.data && flag[1] == false)
			{
				// We get second node n2
				flag[1] = true;
			}
			else if (flag[0] != flag[1])
			{
				this.status = true;
				// Print intermediate inorder nodes
				process.stdout.write(" " + node.data);
			}
			// Visit right subtree
			this.betweenInorder(node.right, n1, n2, flag);
		}
	}
	// Check that given key exists in binary tree
	findNode(node, key)
	{
		if (node == null)
		{
			return false;
		}
		else if (node.data == key)
		{
			// Found the key node then return 1 indicates node exists
			return true;
		}
		else if (this.findNode(node.left, key) 
                 || this.findNode(node.right, key))
		{
			return true;
		}
		return false;
	}
	// This function are use to detect given node
	// n1 and n2 exist or not in binary tree if node exist
	nodeInorder(n1, n2)
	{
		if (this.root == null)
		{
			// When tree is empty
			return;
		}
		if (this.findNode(this.root, n1) 
            && this.findNode(this.root, n2))
		{
			// When both node exists
			// flag are used to indicate node status
			var flag = [false, false];
			this.status = false;
			// Display node value
			process.stdout.write("\n Inorder between (" +
                                 n1 + " " + n2 + ") is\n ");
			// Inorder between n1 and n2
			this.betweenInorder(this.root, n1, n2, flag);
			if (this.status == false)
			{
				process.stdout.write(" None \n");
			}
		}
		else
		{
			process.stdout.write(" \n Given node pair (" + 
                                 n1 + "," + n2 + ") are not exist ");
		}
	}
}

function main()
{
	// Create new binary tree
	var tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	      12    7    
	     / \      \               
	    2   3      1
	       / \    / 
	      6   8  5
	     /     \  
	    9       10    
	-----------------
	  Constructing binary tree
	*/
	tree.root = new TreeNode(4);
	tree.root.left = new TreeNode(12);
	tree.root.left.right = new TreeNode(3);
	tree.root.left.right.left = new TreeNode(6);
	tree.root.left.right.left.left = new TreeNode(9);
	tree.root.left.right.right = new TreeNode(8);
	tree.root.left.right.right.right = new TreeNode(10);
	tree.root.left.left = new TreeNode(2);
	tree.root.right = new TreeNode(7);
	tree.root.right.right = new TreeNode(1);
	tree.root.right.right.left = new TreeNode(5);
	tree.inOrder(tree.root);
	// Test cases
	tree.nodeInorder(2, 10);
	tree.nodeInorder(8, 5);
	tree.nodeInorder(1, 6);
	tree.nodeInorder(3, 6);
	tree.nodeInorder(3, 11);
}
main();

input

 2 12 9 6 3 8 10 4 7 5 1
 Inorder between (2 10) is
  12 9 6 3 8
 Inorder between (8 5) is
  10 4 7
 Inorder between (1 6) is
  3 8 10 4 7 5
 Inorder between (3 6) is
  None

 Given node pair (3,11) are not exist
#    Python 3 Program
#    Inorder traversal between two binary tree nodes

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

class BinaryTree :
	def __init__(self) :
		self.root = None
		self.status = False
	
	#  inorder traversal of binary tree
	def inOrder(self, node) :
		if (node != None) :
			#  Visit left subtree
			self.inOrder(node.left)
			#  Print node value
			print(" ", node.data, end = "")
			#  Visit right subtree
			self.inOrder(node.right)
		
	
	def betweenInorder(self, node, n1, n2, flag) :
		if (node != None) :
			#  Visit left subtree
			self.betweenInorder(node.left, n1, n2, flag)
			if (n1 == node.data and flag[0] == False) :
				#  We get first node n1
				flag[0] = True
			elif (n2 == node.data and flag[1] == False) :
				#  We get second node n2
				flag[1] = True
			elif (flag[0] != flag[1]) :
				self.status = True
				#  Print intermediate inorder nodes
				print(" ", node.data, end = "")
			
			#  Visit right subtree
			self.betweenInorder(node.right, n1, n2, flag)
		
	
	#  Check that given key exists in binary tree
	def findNode(self, node, key) :
		if (node == None) :
			return False
		elif (node.data == key) :
			#  Found the key node then return 1 indicates node exists
			return True
		elif (self.findNode(node.left, key) or 
              self.findNode(node.right, key)) :
			return True
		
		return False
	
	#  This function are use to detect given node
	#  n1 and n2 exist or not in binary tree if node exist
	def nodeInorder(self, n1, n2) :
		if (self.root == None) :
			#  When tree is empty
			return
		
		if (self.findNode(self.root, n1) and 
            self.findNode(self.root, n2)) :
			#  When both node exists
			#  flag are used to indicate node status
			flag = [False, False]
			self.status = False
			#  Display node value
			print("\n Inorder between (", n1 ,"", n2 ,") is\n ", end = "")
			#  Inorder between n1 and n2
			self.betweenInorder(self.root, n1, n2, flag)
			if (self.status == False) :
				print(" None ")
			
		else :
			print(" \n Given node pair (", n1 ,",", 
                  n2 ,") are not exist ", end = "")
		
	

def main() :
	#  Create new binary tree
	tree = BinaryTree()
	#         4                            
	#       /   \    
	#      12    7    
	#     / \      \               
	#    2   3      1
	#       / \    / 
	#      6   8  5
	#     /     \  
	#    9       10    
	# -----------------
	#  Constructing binary tree
	tree.root = TreeNode(4)
	tree.root.left = TreeNode(12)
	tree.root.left.right = TreeNode(3)
	tree.root.left.right.left = TreeNode(6)
	tree.root.left.right.left.left = TreeNode(9)
	tree.root.left.right.right = TreeNode(8)
	tree.root.left.right.right.right = TreeNode(10)
	tree.root.left.left = TreeNode(2)
	tree.root.right = TreeNode(7)
	tree.root.right.right = TreeNode(1)
	tree.root.right.right.left = TreeNode(5)
	tree.inOrder(tree.root)
	#  Test cases
	tree.nodeInorder(2, 10)
	tree.nodeInorder(8, 5)
	tree.nodeInorder(1, 6)
	tree.nodeInorder(3, 6)
	tree.nodeInorder(3, 11)

if __name__ == "__main__": main()

input

  2  12  9  6  3  8  10  4  7  5  1
 Inorder between ( 2  10 ) is
   12  9  6  3  8
 Inorder between ( 8  5 ) is
   10  4  7
 Inorder between ( 1  6 ) is
   3  8  10  4  7  5
 Inorder between ( 3  6 ) is
  None

 Given node pair ( 3 , 11 ) are not exist
#    Ruby Program
#    Inorder traversal between two binary tree nodes

#  Binary Tree node
class TreeNode 
	# Define the accessor and reader of class TreeNode
	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, :status
	attr_accessor :root, :status
	def initialize() 
		self.root = nil
		self.status = false
	end

	#  inorder traversal of binary tree
	def inOrder(node) 
		if (node != nil) 
			#  Visit left subtree
			self.inOrder(node.left)
			#  Print node value
			print(" ", node.data)
			#  Visit right subtree
			self.inOrder(node.right)
		end

	end

	def betweenInorder(node, n1, n2, flag) 
		if (node != nil) 
			#  Visit left subtree
			self.betweenInorder(node.left, n1, n2, flag)
			if (n1 == node.data && flag[0] == false) 
				#  We get first node n1
				flag[0] = true
			elsif (n2 == node.data && flag[1] == false) 
				#  We get second node n2
				flag[1] = true
			elsif (flag[0] != flag[1]) 
				self.status = true
				#  Print intermediate inorder nodes
				print(" ", node.data)
			end

			#  Visit right subtree
			self.betweenInorder(node.right, n1, n2, flag)
		end

	end

	#  Check that given key exists in binary tree
	def findNode(node, key) 
		if (node == nil) 
			return false
		elsif (node.data == key) 
			#  Found the key node then return 1 indicates node exists
			return true
		elsif (self.findNode(node.left, key) || self.findNode(node.right, key)) 
			return true
		end

		return false
	end

	#  This function are use to detect given node
	#  n1 and n2 exist or not in binary tree if node exist
	def nodeInorder(n1, n2) 
		if (self.root == nil) 
			#  When tree is empty
			return
		end

		if (self.findNode(self.root, n1) && self.findNode(self.root, n2)) 
			#  When both node exists
			#  flag are used to indicate node status
			flag = [false, false]
			self.status = false
			#  Display node value
			print("\n Inorder between (", n1 ," ", n2 ,") is\n ")
			#  Inorder between n1 and n2
			self.betweenInorder(self.root, n1, n2, flag)
			if (self.status == false) 
				print(" None \n")
			end

		else
 
			print(" \n Given node pair (", n1 ,",", n2 ,") are not exist ")
		end

	end

end

def main() 
	#  Create new binary tree
	tree = BinaryTree.new()
	#         4                            
	#       /   \    
	#      12    7    
	#     / \      \               
	#    2   3      1
	#       / \    / 
	#      6   8  5
	#     /     \  
	#    9       10    
	# -----------------
	#  Constructing binary tree
	tree.root = TreeNode.new(4)
	tree.root.left = TreeNode.new(12)
	tree.root.left.right = TreeNode.new(3)
	tree.root.left.right.left = TreeNode.new(6)
	tree.root.left.right.left.left = TreeNode.new(9)
	tree.root.left.right.right = TreeNode.new(8)
	tree.root.left.right.right.right = TreeNode.new(10)
	tree.root.left.left = TreeNode.new(2)
	tree.root.right = TreeNode.new(7)
	tree.root.right.right = TreeNode.new(1)
	tree.root.right.right.left = TreeNode.new(5)
	tree.inOrder(tree.root)
	#  Test cases
	tree.nodeInorder(2, 10)
	tree.nodeInorder(8, 5)
	tree.nodeInorder(1, 6)
	tree.nodeInorder(3, 6)
	tree.nodeInorder(3, 11)
end

main()

input

 2 12 9 6 3 8 10 4 7 5 1
 Inorder between (2 10) is
  12 9 6 3 8
 Inorder between (8 5) is
  10 4 7
 Inorder between (1 6) is
  3 8 10 4 7 5
 Inorder between (3 6) is
  None 
 
 Given node pair (3,11) are not exist 
/*
    Scala Program
    Inorder traversal between two binary tree nodes
*/
// Binary Tree node
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		// Set node value
		this(data,null, null);
	}
}
class BinaryTree(var root: TreeNode,
	var status: Boolean)
{
	def this()
	{
		this(null,false);
	}
	// inorder traversal of binary tree
	def inOrder(node: TreeNode): Unit = {
		if (node != null)
		{
			// Visit left subtree
			inOrder(node.left);
			// Print node value
			print(" " + node.data);
			// Visit right subtree
			inOrder(node.right);
		}
	}
	def betweenInorder(node: TreeNode, 
                       n1: Int, n2: Int, flag: Array[Boolean]): Unit = {
		if (node != null)
		{
			// Visit left subtree
			betweenInorder(node.left, n1, n2, flag);
			if (n1 == node.data && flag(0) == false)
			{
				// We get first node n1
				flag(0) = true;
			}
			else if (n2 == node.data && flag(1) == false)
			{
				// We get second node n2
				flag(1) = true;
			}
			else if (flag(0) != flag(1))
			{
				this.status = true;
				// Print intermediate inorder nodes
				print(" " + node.data);
			}
			// Visit right subtree
			betweenInorder(node.right, n1, n2, flag);
		}
	}
	// Check that given key exists in binary tree
	def findNode(node: TreeNode, key: Int): Boolean = {
		if (node == null)
		{
			return false;
		}
		else if (node.data == key)
		{
			// Found the key node then return 1 indicates node exists
			return true;
		}
		else if (findNode(node.left, key) || findNode(node.right, key))
		{
			return true;
		}
		return false;
	}
	// This function are use to detect given node
	// n1 and n2 exist or not in binary tree if node exist
	def nodeInorder(n1: Int, n2: Int): Unit = {
		if (this.root == null)
		{
			// When tree is empty
			return;
		}
		if (findNode(this.root, n1) && findNode(this.root, n2))
		{
			// When both node exists
			// flag are used to indicate node status
			var flag: Array[Boolean] = Array(false, false);
			this.status = false;
			// Display node value
			print("\n Inorder between (" + n1 + " " + n2 + ") is\n ");
			// Inorder between n1 and n2
			betweenInorder(this.root, n1, n2, flag);
			if (this.status == false)
			{
				print(" None \n");
			}
		}
		else
		{
			print(" \n Given node pair (" + n1 + "," + n2 + ") are not exist ");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create new binary tree
		var tree: BinaryTree = new BinaryTree();
		/*
		         4                            
		       /   \    
		      12    7    
		     / \      \               
		    2   3      1
		       / \    / 
		      6   8  5
		     /     \  
		    9       10    
		-----------------
		  Constructing binary tree
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(12);
		tree.root.left.right = new TreeNode(3);
		tree.root.left.right.left = new TreeNode(6);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.right.right.right = new TreeNode(10);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(7);
		tree.root.right.right = new TreeNode(1);
		tree.root.right.right.left = new TreeNode(5);
		tree.inOrder(tree.root);
		// Test cases
		tree.nodeInorder(2, 10);
		tree.nodeInorder(8, 5);
		tree.nodeInorder(1, 6);
		tree.nodeInorder(3, 6);
		tree.nodeInorder(3, 11);
	}
}

input

 2 12 9 6 3 8 10 4 7 5 1
 Inorder between (2 10) is
  12 9 6 3 8
 Inorder between (8 5) is
  10 4 7
 Inorder between (1 6) is
  3 8 10 4 7 5
 Inorder between (3 6) is
  None

 Given node pair (3,11) are not exist
/*
    Swift 4 Program
    Inorder traversal between two binary tree nodes
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		// Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	var status: Bool;
	init()
	{
		self.root = nil;
		self.status = false;
	}
	// inorder traversal of binary tree
	func inOrder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			// Visit left subtree
			self.inOrder(node!.left);
			// Print node value
			print(" ", node!.data, terminator: "");
			// Visit right subtree
			self.inOrder(node!.right);
		}
	}
	func betweenInorder(_ node: TreeNode? , 
                        _ n1 : Int, _ n2: Int, _ flag: inout[Bool])
	{
		if (node  != nil)
		{
			// Visit left subtree
			self.betweenInorder(node!.left, n1, n2, &flag);
			if (n1 == node!.data && flag[0] == false)
			{
				// We get first node n1
				flag[0] = true;
			}
			else if (n2 == node!.data && flag[1] == false)
			{
				// We get second node n2
				flag[1] = true;
			}
			else if (flag[0]  != flag[1])
			{
				self.status = true;
				// Print intermediate inorder nodes
				print(" ", node!.data, terminator: "");
			}
			// Visit right subtree
			self.betweenInorder(node!.right, n1, n2, &flag);
		}
	}
	// Check that given key exists in binary tree
	func findNode(_ node: TreeNode? , _ key : Int) -> Bool
	{
		if (node == nil)
		{
			return false;
		}
		else if (node!.data == key)
		{
			// Found the key node then return 1 indicates node exists
			return true;
		}
		else if (self.findNode(node!.left, key) 
                 || self.findNode(node!.right, key))
		{
			return true;
		}
		return false;
	}
	// This function are use to detect given node
	// n1 and n2 exist or not in binary tree if node exist
	func nodeInorder(_ n1: Int, _ n2: Int)
	{
		if (self.root == nil)
		{
			// When tree is empty
			return;
		}
		if (self.findNode(self.root, n1) && self.findNode(self.root, n2))
		{
			// When both node exists
			// flag are used to indicate node status
			var flag = [false, false];
			self.status = false;
			// Display node value
			print("\n Inorder between (", n1 ,"", n2 ,") is\n ", 
                  terminator: "");
			// Inorder between n1 and n2
			self.betweenInorder(self.root, n1, n2, &flag);
			if (self.status == false)
			{
				print(" None ");
			}
		}
		else
		{
			print(" \n Given node pair (", n1 ,",", n2 ,") are not exist ", terminator: "");
		}
	}
}
func main()
{
	// Create new binary tree
	let tree = BinaryTree();
	/*
	         4                            
	       /   \    
	      12    7    
	     / \      \               
	    2   3      1
	       / \    / 
	      6   8  5
	     /     \  
	    9       10    
	-----------------
	  Constructing binary tree
	*/
	tree.root = TreeNode(4);
	tree.root!.left = TreeNode(12);
	tree.root!.left!.right = TreeNode(3);
	tree.root!.left!.right!.left = TreeNode(6);
	tree.root!.left!.right!.left!.left = TreeNode(9);
	tree.root!.left!.right!.right = TreeNode(8);
	tree.root!.left!.right!.right!.right = TreeNode(10);
	tree.root!.left!.left = TreeNode(2);
	tree.root!.right = TreeNode(7);
	tree.root!.right!.right = TreeNode(1);
	tree.root!.right!.right!.left = TreeNode(5);
	tree.inOrder(tree.root);
	// Test cases
	tree.nodeInorder(2, 10);
	tree.nodeInorder(8, 5);
	tree.nodeInorder(1, 6);
	tree.nodeInorder(3, 6);
	tree.nodeInorder(3, 11);
}
main();

input

  2  12  9  6  3  8  10  4  7  5  1
 Inorder between ( 2  10 ) is
   12  9  6  3  8
 Inorder between ( 8  5 ) is
   10  4  7
 Inorder between ( 1  6 ) is
   3  8  10  4  7  5
 Inorder between ( 3  6 ) is
  None

 Given node pair ( 3 , 11 ) are not exist
/*
    Kotlin Program
    Inorder traversal between two binary tree nodes
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	var root: TreeNode ? ;
	var status: Boolean;
	constructor()
	{
		this.root = null;
		this.status = false;
	}
	// inorder traversal of binary tree
	fun inOrder(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			// Visit left subtree
			this.inOrder(node.left);
			// Print node value
			print(" " + node.data);
			// Visit right subtree
			this.inOrder(node.right);
		}
	}
	fun betweenInorder(node: TreeNode ? , 
                       n1 : Int, n2: Int, flag: Array < Boolean > ): Unit
	{
		if (node != null)
		{
			// Visit left subtree
			this.betweenInorder(node.left, n1, n2, flag);
			if (n1 == node.data && flag[0] == false)
			{
				// We get first node n1
				flag[0] = true;
			}
			else if (n2 == node.data && flag[1] == false)
			{
				// We get second node n2
				flag[1] = true;
			}
			else if (flag[0] != flag[1])
			{
				this.status = true;
				// Print intermediate inorder nodes
				print(" " + node.data);
			}
			// Visit right subtree
			this.betweenInorder(node.right, n1, n2, flag);
		}
	}
	// Check that given key exists in binary tree
	fun findNode(node: TreeNode ? , key : Int): Boolean
	{
		if (node == null)
		{
			return false;
		}
		else if (node.data == key)
		{
			// Found the key node then return 1 indicates node exists
			return true;
		}
		else if (this.findNode(node.left, key) 
                 || this.findNode(node.right, key))
		{
			return true;
		}
		return false;
	}
	// This function are use to detect given node
	// n1 and n2 exist or not in binary tree if node exist
	fun nodeInorder(n1: Int, n2: Int): Unit
	{
		if (this.root == null)
		{
			// When tree is empty
			return;
		}
		if (this.findNode(this.root, n1) 
            && this.findNode(this.root, n2))
		{
			// When both node exists
			// flag are used to indicate node status
			var flag: Array < Boolean > = arrayOf(false, false);
			this.status = false;
			// Display node value
			print("\n Inorder between (" + n1 + " " + n2 + ") is\n ");
			// Inorder between n1 and n2
			this.betweenInorder(this.root, n1, n2, flag);
			if (this.status == false)
			{
				print(" None \n");
			}
		}
		else
		{
			print(" \n Given node pair (" + n1 + "," + n2 + ") are not exist ");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Create new binary tree
	val tree: BinaryTree = BinaryTree();
	/*
	         4                            
	       /   \    
	      12    7    
	     / \      \               
	    2   3      1
	       / \    / 
	      6   8  5
	     /     \  
	    9       10    
	-----------------
	  Constructing binary tree
	*/
	tree.root = TreeNode(4);
	tree.root?.left = TreeNode(12);
	tree.root?.left?.right = TreeNode(3);
	tree.root?.left?.right?.left = TreeNode(6);
	tree.root?.left?.right?.left?.left = TreeNode(9);
	tree.root?.left?.right?.right = TreeNode(8);
	tree.root?.left?.right?.right?.right = TreeNode(10);
	tree.root?.left?.left = TreeNode(2);
	tree.root?.right = TreeNode(7);
	tree.root?.right?.right = TreeNode(1);
	tree.root?.right?.right?.left = TreeNode(5);
	tree.inOrder(tree.root);
	// Test cases
	tree.nodeInorder(2, 10);
	tree.nodeInorder(8, 5);
	tree.nodeInorder(1, 6);
	tree.nodeInorder(3, 6);
	tree.nodeInorder(3, 11);
}

input

 2 12 9 6 3 8 10 4 7 5 1
 Inorder between (2 10) is
  12 9 6 3 8
 Inorder between (8 5) is
  10 4 7
 Inorder between (1 6) is
  3 8 10 4 7 5
 Inorder between (3 6) is
  None

 Given node pair (3,11) are not exist


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