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