Skip to main content

Find distance between two nodes of a Binary Search Tree

Here given code implementation process.

//C Program 
//Find distance between two nodes of a Binary Search Tree
#include <stdio.h>

#include <stdlib.h>
 //structure of Binary Search Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};
//Adding a new node in binary search tree
void add(struct Node **root, int data)
{
	//Create a dynamic node of binary search tree 
	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
		if ( *root == NULL)
		{
			//When adds a first node in binary tree
			*root = new_node;
		}
		else
		{
			struct Node *find = *root;
			//iterate binary tree and add new node to proper position
			while (find != NULL)
			{
				if (find->data > data)
				{
					if (find->left == NULL)
					{
						find->left = new_node;
						break;
					}
					else
					{ //visit left sub-tree
						find = find->left;
					}
				}
				else
				{
					if (find->right == NULL)
					{
						find->right = new_node;
						break;
					}
					else
					{
						//visit right sub-tree
						find = find->right;
					}
				}
			}
		}
	}
	else
	{
		printf("Memory Overflow\n");
		exit(0); //Terminate program execution
	}
}
//Check that whether given binary tree node exists in BST
struct Node *find_node(struct Node *root, int data)
{
	if (root != NULL)
	{
		if (root->data > data)
		{
			return find_node(root->left, data);
		}
		else if (root->data < data)
		{
			return find_node(root->right, data);
		}
		else
		{
			return root;
		}
	}
	return NULL;
}
//Find LCA (parent node) of two given binary tree node
struct Node *lca(struct Node *root, int first, int second)
{
	if (root != NULL)
	{
		if (root->data > first && root->data > second)
		{
			return lca(root->left, first, second);
		}
		else if (root->data < first && root->data < second)
		{
			return lca(root->right, first, second);
		}
		else
		{
			return root;
		}
	}
	return NULL;
}
//Returns the calculating result of path length between given head to tree element
int count_path(struct Node *root, int element)
{
	int counter = 0;
	while (root != NULL)
	{
		if (root->data > element)
		{
			root = root->left;
		}
		else if (root->data < element)
		{
			root = root->right;
		}
		else
		{
			break;
		}
		counter++;
	}
	return counter;
}
//This function are handle the request of finding length distance of two given binary tree nodes
void path_length(struct Node *root, int first, int second)
{
	if (root != NULL)
	{
		//First we are check that given elements are exist or not in BST
		struct Node *node1 = find_node(root, first);
		struct Node *node2 = find_node(root, second);
		if (node1 != NULL && node2 != NULL)
		{
			//When both node are exist
			//Find LCA of two nodes
			struct Node *head = lca(root, first, second);
			int result = 0;
			if (head->data == first)
			{
				//When head is current (first key) node 
				//And need to finding the path between [first key->second key nodes]
				result = count_path(head, second);
			}
			else if (head->data == second)
			{
				//When head is current (second key) node 
				//And need to finding the path between [second key->first key nodes]
				result = count_path(head, first);
			}
			else
			{
				//When first and second is child node of LCA of head node
				result = count_path(head, first) + count_path(head, second);
			}
			printf("Path Length between nodes [%d %d] is : %d\n", first, second, result);
		}
		else
		{
			printf("Node pair [%d %d] are missing\n",first, second);
		}
	}
	else
	{
		printf("\nEmpty BST");
	}
}
int main()
{
	struct Node *root = NULL;
	//Add nodes in binary search tree
	/*
         10
       /   \
      3     19
     / \   /  \
    1   4  14  50
   / \     
 -3   2          

  */
	add( & root, 10);
	add( & root, 3);
	add( & root, 19);
	add( & root, 1);
	add( & root, 4);
	add( & root, -3);
	add( & root, 2);
	add( & root, 14);
	add( & root, 50);
	//Test case
	path_length(root, 2, 14);
	path_length(root, -3, 4);
	path_length(root, 10, 2);
	path_length(root, 3, 2);
	path_length(root, 3, 3);
  	path_length(root, 3, 9);
	return 0;
}

Output

Path Length between nodes [2 14] is : 5
Path Length between nodes [-3 4] is : 3
Path Length between nodes [10 2] is : 3
Path Length between nodes [3 2] is : 2
Path Length between nodes [3 3] is : 0
Node pair [3 9] are missing
/*
  Java Program
  Find distance between two nodes of a Binary Search Tree
*/
//Tree node
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		//Set data value of binary tree node
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	public Node root;
	public BinarySearchTree()
	{
		root = null;
	}
	//insert a node in BST
	public void add(int value)
	{
		//Create a dynamic node of binary search tree 
		Node new_node = new Node(value);
		if (new_node != null)
		{
			if (root == null)
			{
				//When adds a first node in binary tree
				root = new_node;
			}
			else
			{
				Node find = root;
				//add new node to proper position
				while (find != null)
				{
					if (find.data >= value)
					{
						if (find.left == null)
						{
							find.left = new_node;
							break;
						}
						else
						{
							//visit left sub-tree
							find = find.left;
						}
					}
					else
					{
						if (find.right == null)
						{
							find.right = new_node;
							break;
						}
						else
						{
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		}
		else
		{
			System.out.print("\nMemory Overflow\n");
		}
	}
	//Check that whether given binary tree node exists in BST
	public Node find_node(Node root, int data)
	{
		if (root != null)
		{
			if (root.data > data)
			{
				return find_node(root.left, data);
			}
			else if (root.data < data)
			{
				return find_node(root.right, data);
			}
			else
			{
				return root;
			}
		}
		return null;
	}
	//Find LCA (parent node) of two given binary tree node
	public Node lca(Node root, int first, int second)
	{
		if (root != null)
		{
			if (root.data > first && root.data > second)
			{
				return lca(root.left, first, second);
			}
			else if (root.data < first && root.data < second)
			{
				return lca(root.right, first, second);
			}
			else
			{
				return root;
			}
		}
		return null;
	}
	//Returns the calculating result of path length between given head to tree element
	public int count_path(Node root, int element)
	{
		int counter = 0;
		while (root != null)
		{
			if (root.data > element)
			{
				root = root.left;
			}
			else if (root.data < element)
			{
				root = root.right;
			}
			else
			{
				break;
			}
			counter++;
		}
		return counter;
	}
	//This function are handle the request of finding length distance of two given binary tree nodes
	public void path_length(int first, int second)
	{
		if (root != null)
		{
			//First we are check that given elements are exist or not in BST
			Node node1 = find_node(root, first);
			Node node2 = find_node(root, second);
			if (node1 != null && node2 != null)
			{
				//When both node are exist
				//Find LCA of two nodes
				Node head = lca(root, first, second);
				int result = 0;
				if (head.data == first)
				{
					//When head is current (first key) node 
					//And need to finding the path between [first key->second key nodes]
					result = count_path(head, second);
				}
				else if (head.data == second)
				{
					//When head is current (second key) node 
					//And need to finding the path between [second key->first key nodes]
					result = count_path(head, first);
				}
				else
				{
					//When first and second is child node of LCA of head node
					result = count_path(head, first) + count_path(head, second);
				}
				System.out.print("Path Length between nodes [" + first + " " + second + "] is : " + result + "\n");
			}
			else
			{
				System.out.print("Node pair [" + first + " " + second + "] are missing\n");
			}
		}
		else
		{
			System.out.print("\nEmpty BST");
		}
	}
	public static void main(String[] args)
	{
		BinarySearchTree obj = new BinarySearchTree();
		//Add nodes in binary search tree
		/*
               10
             /   \
            3     19
           / \   /  \
          1   4  14  50
         / \     
       -3   2          

        */
		obj.add(10);
		obj.add(3);
		obj.add(19);
		obj.add(1);
		obj.add(4);
		obj.add(-3);
		obj.add(2);
		obj.add(14);
		obj.add(50);
		//Test case
		obj.path_length(2, 14);
		obj.path_length(-3, 4);
		obj.path_length(10, 2);
		obj.path_length(3, 2);
		obj.path_length(3, 3);
		obj.path_length(3, 9);
	}
}

Output

Path Length between nodes [2 14] is : 5
Path Length between nodes [-3 4] is : 3
Path Length between nodes [10 2] is : 3
Path Length between nodes [3 2] is : 2
Path Length between nodes [3 3] is : 0
Node pair [3 9] are missing
/*
  C++ Program
  Find distance between two nodes of a Binary Search Tree
*/
//Tree node
#include<iostream>

using namespace std;
class Node
{
	public: int data;
	Node * left;
	Node * right;
	Node(int data)
	{
		
		//Set data value of binary tree node
		this-> data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinarySearchTree
{
	public: Node * root;

	BinarySearchTree()
	{
		this->root = NULL;
	}
	//insert a node in BST
	void add(int value)
	{
		//Create a dynamic node of binary search tree 
		Node * new_node = new Node(value);
		if (new_node != NULL)
		{
			if (this->root == NULL)
			{
				//When adds a first node in binary tree
				this->root = new_node;
			}
			else
			{
				Node * find = this->root;
				//add new node to proper position
				while (find != NULL)
				{
					if (find->data >= value)
					{
						if (find->left == NULL)
						{
							find->left = new_node;
							break;
						}
						else
						{
							//visit left sub-tree
							find = find->left;
						}
					}
					else
					{
						if (find->right == NULL)
						{
							find->right = new_node;
							break;
						}
						else
						{
							//visit right sub-tree
							find = find->right;
						}
					}
				}
			}
		}
		else
		{
			cout << "\nMemory Overflow\n";
		}
	}
	//Check that whether given binary tree node exists in BST
	Node *find_node(Node * root, int data)
	{
		if (root != NULL)
		{
			if (root->data > data)
			{
				return find_node(root->left, data);
			}
			else if (root->data < data)
			{
				return find_node(root->right, data);
			}
			else
			{
				return root;
			}
		}
		return NULL;
	}
	//Find LCA (parent node) of two given binary tree node
	Node *lca(Node * root, int first, int second)
	{
		if (root != NULL)
		{
			if (root->data > first && root->data > second)
			{
				return lca(root->left, first, second);
			}
			else if (root->data < first && root->data < second)
			{
				return lca(root->right, first, second);
			}
			else
			{
				return root;
			}
		}
		return NULL;
	}
	//Returns the calculating result of path length between given head to tree element
	int count_path(Node * root, int element)
	{
		int counter = 0;
		while (root != NULL)
		{
			if (root->data > element)
			{
				root = root->left;
			}
			else if (root->data < element)
			{
				root = root->right;
			}
			else
			{
				break;
			}
			counter++;
		}
		return counter;
	}
	//This function are handle the request of finding length distance of two given binary tree nodes
	void path_length(int first, int second)
	{
		if (this->root != NULL)
		{
			//First we are check that given elements are exist or not in BST
			Node * node1 = find_node(this->root, first);
			Node * node2 = find_node(this->root, second);
			if (node1 != NULL && node2 != NULL)
			{
				//When both node are exist
				//Find LCA of two nodes
				Node * head = lca(this->root, first, second);
				int result = 0;
				if (head->data == first)
				{
					//When head is current (first key) node 
					//And need to finding the path between [first key->second key nodes]
					result = count_path(head, second);
				}
				else if (head->data == second)
				{
					//When head is current (second key) node 
					//And need to finding the path between [second key->first key nodes]
					result = count_path(head, first);
				}
				else
				{
					//When first and second is child node of LCA of head node
					result = count_path(head, first) + count_path(head, second);
				}
				cout << "Path Length between nodes [" << first << " " << second << "] is : " << result << "\n";
			}
			else
			{
				cout << "Node pair [" << first << " " << second << "] are missing\n";
			}
		}
		else
		{
			cout << "\nEmpty BST";
		}
	}
};
int main()
{
	BinarySearchTree obj ;
	//Add nodes in binary search tree
	/*
	               10
	             /   \
	            3     19
	           / \   /  \
	          1   4  14  50
	         / \     
	       -3   2          

	        */
	obj.add(10);
	obj.add(3);
	obj.add(19);
	obj.add(1);
	obj.add(4);
	obj.add(-3);
	obj.add(2);
	obj.add(14);
	obj.add(50);
	//Test case
	obj.path_length(2, 14);
	obj.path_length(-3, 4);
	obj.path_length(10, 2);
	obj.path_length(3, 2);
	obj.path_length(3, 3);
	obj.path_length(3, 9);
	return 0;
}

Output

Path Length between nodes [2 14] is : 5
Path Length between nodes [-3 4] is : 3
Path Length between nodes [10 2] is : 3
Path Length between nodes [3 2] is : 2
Path Length between nodes [3 3] is : 0
Node pair [3 9] are missing
/*
  C# Program
  Find distance between two nodes of a Binary Search Tree
*/
//Tree node
using System;
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		//Set data value of binary tree node
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	public Node root;
	public BinarySearchTree()
	{
		root = null;
	}
	//insert a node in BST
	public void add(int value)
	{
		//Create a dynamic node of binary search tree 
		Node new_node = new Node(value);
		if (new_node != null)
		{
			if (root == null)
			{
				//When adds a first node in binary tree
				root = new_node;
			}
			else
			{
				Node find = root;
				//add new node to proper position
				while (find != null)
				{
					if (find.data >= value)
					{
						if (find.left == null)
						{
							find.left = new_node;
							break;
						}
						else
						{
							//visit left sub-tree
							find = find.left;
						}
					}
					else
					{
						if (find.right == null)
						{
							find.right = new_node;
							break;
						}
						else
						{
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		}
		else
		{
			Console.Write("\nMemory Overflow\n");
		}
	}
	//Check that whether given binary tree node exists in BST
	public Node find_node(Node root, int data)
	{
		if (root != null)
		{
			if (root.data > data)
			{
				return find_node(root.left, data);
			}
			else if (root.data < data)
			{
				return find_node(root.right, data);
			}
			else
			{
				return root;
			}
		}
		return null;
	}
	//Find LCA (parent node) of two given binary tree node
	public Node lca(Node root, int first, int second)
	{
		if (root != null)
		{
			if (root.data > first && root.data > second)
			{
				return lca(root.left, first, second);
			}
			else if (root.data < first && root.data < second)
			{
				return lca(root.right, first, second);
			}
			else
			{
				return root;
			}
		}
		return null;
	}
	//Returns the calculating result of path length between given head to tree element
	public int count_path(Node root, int element)
	{
		int counter = 0;
		while (root != null)
		{
			if (root.data > element)
			{
				root = root.left;
			}
			else if (root.data < element)
			{
				root = root.right;
			}
			else
			{
				break;
			}
			counter++;
		}
		return counter;
	}
	//This function are handle the request of finding length distance of two given binary tree nodes
	public void path_length(int first, int second)
	{
		if (root != null)
		{
			//First we are check that given elements are exist or not in BST
			Node node1 = find_node(root, first);
			Node node2 = find_node(root, second);
			if (node1 != null && node2 != null)
			{
				//Find LCA of two nodes
				Node head = lca(root, first, second);
				int result = 0;
				if (head.data == first)
				{
					//And need to finding the path between [first key->second key nodes]
					result = count_path(head, second);
				}
				else if (head.data == second)
				{
					//And need to finding the path between [second key->first key nodes]
					result = count_path(head, first);
				}
				else
				{
					//When first and second is child node of LCA of head node
					result = count_path(head, first) + count_path(head, second);
				}
				Console.Write("Path Length between nodes [" + first + " " + second + "] is : " + result + "\n");
			}
			else
			{
				Console.Write("Node pair [" + first + " " + second + "] are missing\n");
			}
		}
		else
		{
			Console.Write("\nEmpty BST");
		}
	}
	public static void Main(String[] args)
	{
		BinarySearchTree obj = new BinarySearchTree();
		/*
		               10
		             /   \
		            3     19
		           / \   /  \
		          1   4  14  50
		         / \     
		       -3   2          

		        */
		obj.add(10);
		obj.add(3);
		obj.add(19);
		obj.add(1);
		obj.add(4);
		obj.add(-3);
		obj.add(2);
		obj.add(14);
		obj.add(50);
		//Test case
		obj.path_length(2, 14);
		obj.path_length(-3, 4);
		obj.path_length(10, 2);
		obj.path_length(3, 2);
		obj.path_length(3, 3);
		obj.path_length(3, 9);
	}
}

Output

Path Length between nodes [2 14] is : 5
Path Length between nodes [-3 4] is : 3
Path Length between nodes [10 2] is : 3
Path Length between nodes [3 2] is : 2
Path Length between nodes [3 3] is : 0
Node pair [3 9] are missing
<?php
/*
  Php Program
  Find distance between two nodes of a Binary Search Tree
*/
//Tree node
class Node
{
	public $data;
	public $left;
	public $right;

	function __construct($data)
	{
		//Set data value of binary tree node
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
class BinarySearchTree
{
	public $root;

	function __construct()
	{
		$this->root = null;
	}
	//insert a node in BST
	function add($value)
	{
		//Create a dynamic node of binary search tree 
		$new_node = new Node($value);
		if ($new_node != null)
		{
			if ($this->root == null)
			{
				//When adds a first node in binary tree
				$this->root = $new_node;
			}
			else
			{
				$find = $this->root;
				//add new node to proper position
				while ($find != null)
				{
					if ($find->data >= $value)
					{
						if ($find->left == null)
						{
							$find->left = $new_node;
							break;
						}
						else
						{
							//visit left sub-tree
							$find = $find->left;
						}
					}
					else
					{
						if ($find->right == null)
						{
							$find->right = $new_node;
							break;
						}
						else
						{
							//visit right sub-tree
							$find = $find->right;
						}
					}
				}
			}
		}
		else
		{
			echo "\nMemory Overflow\n";
		}
	}
	//Check that whether given binary tree node exists in BST
	function find_node($root, $data)
	{
		if ($root != null)
		{
			if ($root->data > $data)
			{
				return $this->find_node($root->left, $data);
			}
			else if ($root->data < $data)
			{
				return $this->find_node($root->right, $data);
			}
			else
			{
				return $root;
			}
		}
		return null;
	}
	//Find LCA (parent node) of two given binary tree node
	function lca($root, $first, $second)
	{
		if ($root != null)
		{
			if ($root->data > $first && $root->data > $second)
			{
				return $this->lca($root->left, $first, $second);
			}
			else if ($root->data < $first && $root->data < $second)
			{
				return $this->lca($root->right, $first, $second);
			}
			else
			{
				return $root;
			}
		}
		return null;
	}
	//Returns the calculating result of path length between given head to tree element
	function count_path($root, $element)
	{
		$counter = 0;
		while ($root != null)
		{
			if ($root->data > $element)
			{
				$root = $root->left;
			}
			else if ($root->data < $element)
			{
				$root = $root->right;
			}
			else
			{
				break;
			}
			$counter++;
		}
		return $counter;
	}
	//This function are handle the request of finding length distance of two given binary tree nodes
	function path_length($first, $second)
	{
		if ($this->root != null)
		{
			//First we are check that given elements are exist or not in BST
			$node1 = $this->find_node($this->root, $first);
			$node2 = $this->find_node($this->root, $second);
			if ($node1 != null && $node2 != null)
			{
				//Find LCA of two nodes
				$head = $this->lca($this->root, $first, $second);
				$result = 0;
				if ($head->data == $first)
				{
					//And need to finding the path between [first key->second key nodes]
					$result = $this->count_path($head, $second);
				}
				else if ($head->data == $second)
				{
					//And need to finding the path between [second key->first key nodes]
					$result = $this->count_path($head, $first);
				}
				else
				{
					//When first and second is child node of LCA of head node
					$result = $this->count_path($head, $first) + $this->count_path($head, $second);
				}
				echo "Path Length between nodes [". $first ." ". $second ."] is : ". $result ."\n";
			}
			else
			{
				echo "Node pair [". $first ." ". $second ."] are missing\n";
			}
		}
		else
		{
			echo "\nEmpty BST";
		}
	}
}

function main()
{
	$obj = new BinarySearchTree();
	/*
	               10
	             /   \
	            3     19
	           / \   /  \
	          1   4  14  50
	         / \     
	       -3   2          

	        */
	$obj->add(10);
	$obj->add(3);
	$obj->add(19);
	$obj->add(1);
	$obj->add(4);
	$obj->add(-3);
	$obj->add(2);
	$obj->add(14);
	$obj->add(50);
	//Test case
	$obj->path_length(2, 14);
	$obj->path_length(-3, 4);
	$obj->path_length(10, 2);
	$obj->path_length(3, 2);
	$obj->path_length(3, 3);
	$obj->path_length(3, 9);
}
main();

Output

Path Length between nodes [2 14] is : 5
Path Length between nodes [-3 4] is : 3
Path Length between nodes [10 2] is : 3
Path Length between nodes [3 2] is : 2
Path Length between nodes [3 3] is : 0
Node pair [3 9] are missing
/*
  Node Js Program
  Find distance between two nodes of a Binary Search Tree
*/
//Tree node
class Node
{
	constructor(data)
	{
		//Set data value of binary tree node
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	constructor()
	{
		this.root = null;
	}
	//insert a node in BST
	add(value)
	{
		//Create a dynamic node of binary search tree 
		var new_node = new Node(value);
		if (new_node != null)
		{
			if (this.root == null)
			{
				//When adds a first node in binary tree
				this.root = new_node;
			}
			else
			{
				var find = this.root;
				//add new node to proper position
				while (find != null)
				{
					if (find.data >= value)
					{
						if (find.left == null)
						{
							find.left = new_node;
							break;
						}
						else
						{
							//visit left sub-tree
							find = find.left;
						}
					}
					else
					{
						if (find.right == null)
						{
							find.right = new_node;
							break;
						}
						else
						{
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		}
		else
		{
			process.stdout.write("\nMemory Overflow\n");
		}
	}
	//Check that whether given binary tree node exists in BST
	find_node(root, data)
	{
		if (root != null)
		{
			if (root.data > data)
			{
				return this.find_node(root.left, data);
			}
			else if (root.data < data)
			{
				return this.find_node(root.right, data);
			}
			else
			{
				return root;
			}
		}
		return null;
	}
	//Find LCA (parent node) of two given binary tree node
	lca(root, first, second)
	{
		if (root != null)
		{
			if (root.data > first && root.data > second)
			{
				return this.lca(root.left, first, second);
			}
			else if (root.data < first && root.data < second)
			{
				return this.lca(root.right, first, second);
			}
			else
			{
				return root;
			}
		}
		return null;
	}
	//Returns the calculating result of path length between given head to tree element
	count_path(root, element)
	{
		var counter = 0;
		while (root != null)
		{
			if (root.data > element)
			{
				root = root.left;
			}
			else if (root.data < element)
			{
				root = root.right;
			}
			else
			{
				break;
			}
			counter++;
		}
		return counter;
	}
	//This function are handle the request of finding length distance of two given binary tree nodes
	path_length(first, second)
	{
		if (this.root != null)
		{
			//First we are check that given elements are exist or not in BST
			var node1 = this.find_node(this.root, first);
			var node2 = this.find_node(this.root, second);
			if (node1 != null && node2 != null)
			{
				//When both node are exist
				//Find LCA of two nodes
				var head = this.lca(this.root, first, second);
				var result = 0;
				if (head.data == first)
				{
					//When head is current (first key) node 
					//And need to finding the path between [first key->second key nodes]
					result = this.count_path(head, second);
				}
				else if (head.data == second)
				{
					//When head is current (second key) node 
					//And need to finding the path between [second key->first key nodes]
					result = this.count_path(head, first);
				}
				else
				{
					//When first and second is child node of LCA of head node
					result = this.count_path(head, first) + this.count_path(head, second);
				}
				process.stdout.write("Path Length between nodes [" + first + " " + second + "] is : " + result + "\n");
			}
			else
			{
				process.stdout.write("Node pair [" + first + " " + second + "] are missing\n");
			}
		}
		else
		{
			process.stdout.write("\nEmpty BST");
		}
	}
}

function main()
{
	var obj = new BinarySearchTree();
	//Add nodes in binary search tree
	/*
	               10
	             /   \
	            3     19
	           / \   /  \
	          1   4  14  50
	         / \     
	       -3   2          

	        */
	obj.add(10);
	obj.add(3);
	obj.add(19);
	obj.add(1);
	obj.add(4);
	obj.add(-3);
	obj.add(2);
	obj.add(14);
	obj.add(50);
	//Test case
	obj.path_length(2, 14);
	obj.path_length(-3, 4);
	obj.path_length(10, 2);
	obj.path_length(3, 2);
	obj.path_length(3, 3);
	obj.path_length(3, 9);
}
main();

Output

Path Length between nodes [2 14] is : 5
Path Length between nodes [-3 4] is : 3
Path Length between nodes [10 2] is : 3
Path Length between nodes [3 2] is : 2
Path Length between nodes [3 3] is : 0
Node pair [3 9] are missing
#   Python 3 Program
#   Find distance between two nodes of a Binary Search Tree

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

class BinarySearchTree :
	
	def __init__(self) :
		self.root = None
	
	# insert a node in BST
	def add(self, value) :
		# Create a dynamic node of binary search tree 
		new_node = Node(value)
		if (new_node != None) :
			if (self.root == None) :
				# When adds a first node in binary tree
				self.root = new_node
			else :
				find = self.root
				# add new node to proper position
				while (find != None) :
					if (find.data >= value) :
						if (find.left == None) :
							find.left = new_node
							break
						else :
							# visit left sub-tree
							find = find.left
						
					else :
						if (find.right == None) :
							find.right = new_node
							break
						else :
							# visit right sub-tree
							find = find.right
						
					
				
			
		else :
			print("\nMemory Overflow\n", end = "")
		
	
	# Check that whether given binary tree node exists in BST
	def find_node(self, root, data) :
		if (root != None) :
			if (root.data > data) :
				return self.find_node(root.left, data)
			
			elif(root.data < data) :
				return self.find_node(root.right, data)
			else :
				return root
			
		
		return None
	
	# Find LCA (parent node) of two given binary tree node
	def lca(self, root, first, second) :
		if (root != None) :
			if (root.data > first and root.data > second) :
				return self.lca(root.left, first, second)
			
			elif(root.data < first and root.data < second) :
				return self.lca(root.right, first, second)
			else :
				return root
			
		
		return None
	
	# Returns the calculating result of path length between given head to tree element
	def count_path(self, root, element) :
		counter = 0
		while (root != None) :
			if (root.data > element) :
				root = root.left
			
			elif(root.data < element) :
				root = root.right
			else :
				break
			
			counter += 1
		
		return counter
	
	# This function are handle the request of finding length distance of two given binary tree nodes
	def path_length(self, first, second) :
		if (self.root != None) :
			# First we are check that given elements are exist or not in BST
			node1 = self.find_node(self.root, first)
			node2 = self.find_node(self.root, second)
			if (node1 != None and node2 != None) :
				# When both node are exist
				# Find LCA of two nodes
				head = self.lca(self.root, first, second)
				result = 0
				if (head.data == first) :
					# When head is current (first key) node 
					# And need to finding the path between [first key->second key nodes]
					result = self.count_path(head, second)
				
				elif(head.data == second) :
					# When head is current (second key) node 
					# And need to finding the path between [second key->first key nodes]
					result = self.count_path(head, first)
				else :
					# When first and second is child node of LCA of head node
					result = self.count_path(head, first) + self.count_path(head, second)
				
				print("Path Length between nodes [", first ," ", second ,"] is : ", result ,"\n", end = "")
			else :
				print("Node pair [", first ," ", second ,"] are missing\n", end = "")
			
		else :
			print("\nEmpty BST", end = "")
		
	

def main() :
	obj = BinarySearchTree()
	# Add nodes in binary search tree
	# 
	#                10
	#              /   \
	#             3     19
	#            / \   /  \
	#           1   4  14  50
	#          / \     
	#        -3   2          
	#         
	
	obj.add(10)
	obj.add(3)
	obj.add(19)
	obj.add(1)
	obj.add(4)
	obj.add(-3)
	obj.add(2)
	obj.add(14)
	obj.add(50)
	# Test case
	obj.path_length(2, 14)
	obj.path_length(-3, 4)
	obj.path_length(10, 2)
	obj.path_length(3, 2)
	obj.path_length(3, 3)
	obj.path_length(3, 9)

if __name__ == "__main__": main()

Output

Path Length between nodes [ 2   14 ] is :  5
Path Length between nodes [ -3   4 ] is :  3
Path Length between nodes [ 10   2 ] is :  3
Path Length between nodes [ 3   2 ] is :  2
Path Length between nodes [ 3   3 ] is :  0
Node pair [ 3   9 ] are missing
#   Ruby Program
#   Find distance between two nodes of a Binary Search Tree

# 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 data value of binary tree node
		self.data = data
		self.left = nil
		self.right = nil
	end
end
class BinarySearchTree 

	# Define the accessor and reader of class BinarySearchTree  
	attr_reader :root
	attr_accessor :root

	def initialize()
	
		@root = nil
	end
	# insert a node in BST
	def add(value)
	
		# Create a dynamic node of binary search tree 
		new_node = Node.new(value)
		if (new_node != nil)
		
			if (@root == nil)
			
				# When adds a first node in binary tree
				@root = new_node
			else
			
				find = @root
				# add new node to proper position
				while (find != nil)
				
					if (find.data >= value)
					
						if (find.left == nil)
						
							find.left = new_node
							break
						else
						
							# visit left sub-tree
							find = find.left
						end
					else
					
						if (find.right == nil)
						
							find.right = new_node
							break
						else
						
							# visit right sub-tree
							find = find.right
						end
					end
				end
			end
		else
		
			print("\nMemory Overflow\n")
		end
	end
	# Check that whether given binary tree node exists in BST
	def find_node(root, data)
	
		if (root != nil)
		
			if (root.data > data)
			
				return self.find_node(root.left, data)
			elsif(root.data < data)
			
				return self.find_node(root.right, data)
			else
			
				return root
			end
		end
		return nil
	end
	# Find LCA (parent node) of two given binary tree node
	def lca(root, first, second)
	
		if (root != nil)
		
			if (root.data > first && root.data > second)
			
				return self.lca(root.left, first, second)
			elsif(root.data < first && root.data < second)
			
				return self.lca(root.right, first, second)
			else
			
				return root
			end
		end
		return nil
	end
	# Returns the calculating result of path length between given head to tree element
	def count_path(root, element)
	
		counter = 0
		while (root != nil)
		
			if (root.data > element)
			
				root = root.left
			elsif(root.data < element)
			
				root = root.right
			else
			
				break
			end
			counter += 1
		end
		return counter
	end
	# This function are handle the request of finding length distance of two given binary tree nodes
	def path_length(first, second)
	
		if (@root != nil)
		
			# First we are check that given elements are exist or not in BST
			node1 = self.find_node(@root, first)
			node2 = self.find_node(@root, second)
			if (node1 != nil && node2 != nil)
			
				# When both node are exist
				# Find LCA of two nodes
				head = self.lca(@root, first, second)
				result = 0
				if (head.data == first)
				
					# When head is current (first key) node 
					# And need to finding the path between [first key->second key nodes]
					result = self.count_path(head, second)
				elsif(head.data == second)
				
					# When head is current (second key) node 
					# And need to finding the path between [second key->first key nodes]
					result = self.count_path(head, first)
				else
				
					# When first and second is child node of LCA of head node
					result = self.count_path(head, first) + self.count_path(head, second)
				end
				print("Path Length between nodes [", first ," ", second ,"] is : ", result ,"\n")
			else
			
				print("Node pair [", first ," ", second ,"] are missing\n")
			end
		else
		
			print("\nEmpty BST")
		end
	end
end
def main()

	obj = BinarySearchTree.new()
	# Add nodes in binary search tree
	# 
	#                10
	#              /   \
	#             3     19
	#            / \   /  \
	#           1   4  14  50
	#          / \     
	#        -3   2          
	#         
	
	obj.add(10)
	obj.add(3)
	obj.add(19)
	obj.add(1)
	obj.add(4)
	obj.add(-3)
	obj.add(2)
	obj.add(14)
	obj.add(50)
	# Test case
	obj.path_length(2, 14)
	obj.path_length(-3, 4)
	obj.path_length(10, 2)
	obj.path_length(3, 2)
	obj.path_length(3, 3)
	obj.path_length(3, 9)
end
main()

Output

Path Length between nodes [2 14] is : 5
Path Length between nodes [-3 4] is : 3
Path Length between nodes [10 2] is : 3
Path Length between nodes [3 2] is : 2
Path Length between nodes [3 3] is : 0
Node pair [3 9] are missing
/*
  Scala Program
  Find distance between two nodes of a Binary Search Tree
*/
//Tree node
class Node(var data: Int,
	var left: Node,
		var right: Node)
{
	def this(data: Int)
	{
		//Set data value of binary tree node
		this(data,null,null);
	}
}
class BinarySearchTree(var root: Node)
{
	def this()
	{
		this(null);
	}
	//insert a node in BST
	def add(value: Int): Unit = {
		//Create a dynamic node of binary search tree 
		var new_node: Node = new Node(value);
		if (new_node != null)
		{
			if (root == null)
			{
				//When adds a first node in binary tree
				root = new_node;
			}
			else
			{
				var find: Node = root;
				//add new node to proper position
				while (find != null)
				{
					if (find.data >= value)
					{
						if (find.left == null)
						{
							find.left = new_node;
							return ;
						}
						else
						{
							//visit left sub-tree
							find = find.left;
						}
					}
					else
					{
						if (find.right == null)
						{
							find.right = new_node;
							return ;
						}
						else
						{
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		}
		else
		{
			print("\nMemory Overflow\n");
		}
	}
	//Check that whether given binary tree node exists in BST
	def find_node(root: Node, data: Int): Node = {
		if (root != null)
		{
			if (root.data > data)
			{
				return find_node(root.left, data);
			}
			else if (root.data < data)
			{
				return find_node(root.right, data);
			}
			else
			{
				return root;
			}
		}
		return null;
	}
	//Find LCA (parent node) of two given binary tree node
	def lca(root: Node, first: Int, second: Int): Node = {
		if (root != null)
		{
			if (root.data > first && root.data > second)
			{
				return lca(root.left, first, second);
			}
			else if (root.data < first && root.data < second)
			{
				return lca(root.right, first, second);
			}
			else
			{
				return root;
			}
		}
		return null;
	}
	//Returns the calculating result of path length between given head to tree element
	def count_path(head: Node, element: Int): Int = {
		var counter: Int = 0;
        var root : Node = head;
		while (root != null)
		{
			if (root.data > element)
			{
				root = root.left;
			}
			else if (root.data < element)
			{
				root = root.right;
			}
			else
			{
				return counter;
			}
			counter += 1;
		}
		return counter;
	}
	//This function are handle the request of finding length distance of two given binary tree nodes
	def path_length(first: Int, second: Int): Unit = {
		if (root != null)
		{
			//First we are check that given elements are exist or not in BST
			var node1: Node = find_node(root, first);
			var node2: Node = find_node(root, second);
			if (node1 != null && node2 != null)
			{
				//When both node are exist
				//Find LCA of two nodes
				var head: Node = lca(root, first, second);
				var result: Int = 0;
				if (head.data == first)
				{
					//When head is current (first key) node 
					//And need to finding the path between [first key->second key nodes]
					result = count_path(head, second);
				}
				else if (head.data == second)
				{
					//When head is current (second key) node 
					//And need to finding the path between [second key->first key nodes]
					result = count_path(head, first);
				}
				else
				{
					//When first and second is child node of LCA of head node
					result = count_path(head, first) + count_path(head, second);
				}
				print("Path Length between nodes [" + first + " " + second + "] is : " + result + "\n");
			}
			else
			{
				print("Node pair [" + first + " " + second + "] are missing\n");
			}
		}
		else
		{
			print("\nEmpty BST");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: BinarySearchTree = new BinarySearchTree();
		//Add nodes in binary search tree
		/*
		               10
		             /   \
		            3     19
		           / \   /  \
		          1   4  14  50
		         / \     
		       -3   2          

		        */
		obj.add(10);
		obj.add(3);
		obj.add(19);
		obj.add(1);
		obj.add(4);
		obj.add(-3);
		obj.add(2);
		obj.add(14);
		obj.add(50);
		//Test case
		obj.path_length(2, 14);
		obj.path_length(-3, 4);
		obj.path_length(10, 2);
		obj.path_length(3, 2);
		obj.path_length(3, 3);
		obj.path_length(3, 9);
	}
}

Output

Path Length between nodes [2 14] is : 5
Path Length between nodes [-3 4] is : 3
Path Length between nodes [10 2] is : 3
Path Length between nodes [3 2] is : 2
Path Length between nodes [3 3] is : 0
Node pair [3 9] are missing
/*
  Swift Program
  Find distance between two nodes of a Binary Search Tree
*/
//Tree node
class Node
{
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  init(_ data: Int)
  {
    //Set data value of binary tree node
    self.data = data;
    self.left = nil;
    self.right = nil;
  }
}
class BinarySearchTree
{
  var root: Node? ;
  init()
  {
    self.root = nil;
  }
  //insert a node in BST
  func add(_ value: Int)
  {
    //Create a dynamic node of binary search tree 
    let new_node: Node? = Node(value);
    if (new_node != nil)
    {
      if (self.root == nil)
      {
        //When adds a first node in binary tree
        self.root = new_node;
      }
      else
      {
        var find: Node? = self.root;
        //add new node to proper position
        while (find != nil)
        {
          if (find!.data >= value)
          {
            if (find!.left == nil)
            {
              find!.left = new_node;
              break;
            }
            else
            {
              //visit left sub-tree
              find = find!.left;
            }
          }
          else
          {
            if (find!.right == nil)
            {
              find!.right = new_node;
              break;
            }
            else
            {
              //visit right sub-tree
              find = find!.right;
            }
          }
        }
      }
    }
    else
    {
      print("\nMemory Overflow\n", terminator: "");
    }
  }
  //Check that whether given binary tree node exists in BST
  func find_node(_ root: Node? , _ data : Int) -> Node?
  {
    if (root != nil)
    {
      if (root!.data > data)
      {
        return self.find_node(root!.left, data);
      }
      else if (root!.data < data)
      {
        return self.find_node(root!.right, data);
      }
      else
      {
        return root;
      }
    }
    return nil;
  }
  //Find LCA (parent node) of two given binary tree node
  func lca(_ root: Node? , _ first : Int, _ second: Int) -> Node?
  {
    if (root != nil)
    {
      if (root!.data > first && root!.data > second)
      {
        return self.lca(root!.left, first, second);
      }
      else if (root!.data < first && root!.data < second)
      {
        return self.lca(root!.right, first, second);
      }
      else
      {
        return root;
      }
    }
    return nil;
  }
  //Returns the calculating result of path length between given head to tree element
  func count_path(_ head: Node? , _ element : Int) -> Int
  {
    var counter: Int = 0;
    var temp : Node? = head;
    while (temp != nil)
    {
      if (temp!.data > element)
      {
        temp = temp!.left;
      }
      else if (temp!.data < element)
      {
        temp = temp!.right;
      }
      else
      {
        break;
      }
      counter += 1;
    }
    return counter;
  }
  //This function are handle the request of finding length distance of two given binary tree nodes
  func path_length(_ first: Int, _ second: Int)
  {
    if (self.root != nil)
    {
      //First we are check that given elements are exist or not in BST
      let node1: Node? = self.find_node(self.root, first);
      let node2: Node? = self.find_node(self.root, second);
      if (node1 != nil && node2 != nil)
      {
        //When both node are exist
        //Find LCA of two nodes
        let head: Node? = self.lca(self.root, first, second);
        var result: Int = 0;
        if (head!.data == first)
        {
          //When head is current (first key) node 
          //And need to finding the path between [first key->second key nodes]
          result = self.count_path(head, second);
        }
        else if (head!.data == second)
        {
          //When head is current (second key) node 
          //And need to finding the path between [second key->first key nodes]
          result = self.count_path(head, first);
        }
        else
        {
          //When first and second is child node of LCA of head node
          result = self.count_path(head, first) + self.count_path(head, second);
        }
        print("Path Length between nodes [", first ," ", second ,"] is : ", result ,"\n", terminator: "");
      }
      else
      {
        print("Node pair [", first ," ", second ,"] are missing\n", terminator: "");
      }
    }
    else
    {
      print("\nEmpty BST", terminator: "");
    }
  }
}
func main()
{
  let obj: BinarySearchTree = BinarySearchTree();
  //Add nodes in binary search tree
  /*
                 10
               /   \
              3     19
             / \   /  \
            1   4  14  50
           / \     
         -3   2          

          */
  obj.add(10);
  obj.add(3);
  obj.add(19);
  obj.add(1);
  obj.add(4);
  obj.add(-3);
  obj.add(2);
  obj.add(14);
  obj.add(50);
  //Test case
  obj.path_length(2, 14);
  obj.path_length(-3, 4);
  obj.path_length(10, 2);
  obj.path_length(3, 2);
  obj.path_length(3, 3);
  obj.path_length(3, 9);
}
main();

Output

Path Length between nodes [ 2   14 ] is :  5
Path Length between nodes [ -3   4 ] is :  3
Path Length between nodes [ 10   2 ] is :  3
Path Length between nodes [ 3   2 ] is :  2
Path Length between nodes [ 3   3 ] is :  0
Node pair [ 3   9 ] are missing




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