Random traversal of binary search tree
Here given code implementation process.
//C Program
//Random traversal in Binary search tree
#include <stdio.h>
#include <stdlib.h>
#include <time.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;
//Initially node left-pointer is NULL
new_node->left = NULL;
//Initially node right-pointer is NULL
new_node->right = 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
}
}
//Traverse the random nodes in given binary search tree
void random_traversal(struct Node *root)
{
if (root != NULL)
{
//Check whether random number is Even or not
if (rand() % 2 == 0)
{
//When visiting on left subtree first
random_traversal(root->left);
//display node value
printf("%3d ", root->data);
//When visiting on right subtree second
random_traversal(root->right);
}
else
{
//When visiting on right subtree first
random_traversal(root->right);
//display node value
printf("%3d ", root->data);
//When visiting on left subtree second
random_traversal(root->left);
}
}
}
int main()
{
srand(time(NULL));
struct Node *root = NULL;
//Add nodes in binary search tree
/*
6
/ \
/ \
3 9
/ \ / \
1 5 7 20
/ /
4 15
*/
add( & root, 6);
add( & root, 3);
add( & root, 9);
add( & root, 1);
add( & root, 5);
add( & root, 7);
add( & root, 4);
add( & root, 15);
random_traversal(root);
printf("\n");
random_traversal(root);
printf("\n");
random_traversal(root);
printf("\n");
random_traversal(root);
return 0;
}
Output
1 3 4 5 6 15 9 7
5 4 3 1 6 7 9 15
7 9 15 6 5 4 3 1
1 3 5 4 6 7 9 15
/*
Java Program
Random traversal in Binary search tree
*/
import java.util.Random;
//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 Random rand;
public BinarySearchTree()
{
root = null;
rand = new Random();
}
//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");
}
}
//Traverse the random nodes in given binary search tree
public void random_traversal(Node head)
{
if (head != null)
{
if (rand.nextInt() % 2 == 0)
{
//When visiting on left subtree first
random_traversal(head.left);
System.out.print(" " + head.data + " ");
//When visiting on right subtree second
random_traversal(head.right);
}
else
{
//When visiting on right subtree first
random_traversal(head.right);
System.out.print(" " + head.data + " ");
//When visiting on left subtree second
random_traversal(head.left);
}
}
}
public static void main(String[] args)
{
BinarySearchTree obj = new BinarySearchTree();
//Add nodes in binary search tree
/*
6
/ \
/ \
3 9
/ \ / \
1 5 7 20
/ /
4 15
*/
obj.add(6);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(5);
obj.add(7);
obj.add(4);
obj.add(15);
obj.random_traversal(obj.root);
System.out.print("\n");
obj.random_traversal(obj.root);
System.out.print("\n");
obj.random_traversal(obj.root);
System.out.print("\n");
obj.random_traversal(obj.root);
}
}
Output
7 9 15 6 4 5 3 1
1 3 4 5 6 7 9 15
15 9 7 6 1 3 5 4
5 4 3 1 6 15 9 7
/*
C++ Program
Random traversal in Binary search tree
*/
#include<iostream>
#include<time.h>
#include<stdlib.h>
using namespace std;;
//Tree node
class Node
{
public: int data;
Node * left;
Node * right;
Node(int data)
{
this ->
//Set data value of binary tree node
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";
}
}
//Traverse the random nodes in given binary search tree
void random_traversal(Node * head)
{
if (head != NULL)
{
if (rand() % 2 == 0)
{
//When visiting on left subtree first
random_traversal(head->left);
cout << " " << head->data << " ";
//When visiting on right subtree second
random_traversal(head->right);
}
else
{
//When visiting on right subtree first
random_traversal(head->right);
cout << " " << head->data << " ";
//When visiting on left subtree second
random_traversal(head->left);
}
}
}
};
int main()
{
srand(time(NULL));
BinarySearchTree obj ;
//Add nodes in binary search tree
/*
6
/ \
/ \
3 9
/ \ / \
1 5 7 20
/ /
4 15
*/
obj.add(6);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(5);
obj.add(7);
obj.add(4);
obj.add(15);
obj.random_traversal(obj.root);
cout << "\n";
obj.random_traversal(obj.root);
cout << "\n";
obj.random_traversal(obj.root);
cout << "\n";
obj.random_traversal(obj.root);
return 0;
}
Output
15 9 7 6 1 3 4 5
1 3 4 5 6 7 9 15
7 9 15 6 1 3 5 4
4 5 3 1 6 15 9 7
//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 Random rand;
public BinarySearchTree()
{
root = null;
rand = new Random();
}
//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");
}
}
//Traverse the random nodes in given binary search tree
public void random_traversal(Node head)
{
if (head != null)
{
if (rand.Next() % 2 == 0)
{
//When visiting on left subtree first
random_traversal(head.left);
Console.Write(" " + head.data + " ");
//When visiting on right subtree second
random_traversal(head.right);
}
else
{
//When visiting on right subtree first
random_traversal(head.right);
Console.Write(" " + head.data + " ");
//When visiting on left subtree second
random_traversal(head.left);
}
}
}
public static void Main(String[] args)
{
BinarySearchTree obj = new BinarySearchTree();
/*
6
/ \
/ \
3 9
/ \ / \
1 5 7 20
/ /
4 15
*/
obj.add(6);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(5);
obj.add(7);
obj.add(4);
obj.add(15);
obj.random_traversal(obj.root);
Console.Write("\n");
obj.random_traversal(obj.root);
Console.Write("\n");
obj.random_traversal(obj.root);
Console.Write("\n");
obj.random_traversal(obj.root);
}
}
Output
4 5 3 1 6 15 9 7
15 9 7 6 1 3 4 5
7 9 15 6 4 5 3 1
1 3 5 4 6 7 9 15
<?php
//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";
}
}
//Traverse the random nodes in given binary search tree
function random_traversal($head)
{
if ($head != null)
{
if (rand() % 2 == 0)
{
//When visiting on left subtree first
$this->random_traversal($head->left);
echo " ". $head->data ." ";
//When visiting on right subtree second
$this->random_traversal($head->right);
}
else
{
//When visiting on right subtree first
$this->random_traversal($head->right);
echo " ". $head->data ." ";
//When visiting on left subtree second
$this->random_traversal($head->left);
}
}
}
}
function main()
{
$obj = new BinarySearchTree();
/*
6
/ \
/ \
3 9
/ \ / \
1 5 7 20
/ /
4 15
*/
$obj->add(6);
$obj->add(3);
$obj->add(9);
$obj->add(1);
$obj->add(5);
$obj->add(7);
$obj->add(4);
$obj->add(15);
$obj->random_traversal($obj->root);
echo "\n";
$obj->random_traversal($obj->root);
echo "\n";
$obj->random_traversal($obj->root);
echo "\n";
$obj->random_traversal($obj->root);
}
main();
Output
1 3 4 5 6 15 9 7
7 9 15 6 4 5 3 1
15 9 7 6 5 4 3 1
1 3 5 4 6 7 9 15
//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");
}
}
//Traverse the random nodes in given binary search tree
random_traversal(head)
{
if (head != null)
{
// RANDOM number between 0 to 100
if ( Math.floor(Math.random() * 100) %2 == 0)
{
//When visiting on left subtree first
this.random_traversal(head.left);
process.stdout.write(" " + head.data + " ");
//When visiting on right subtree second
this.random_traversal(head.right);
}
else
{
//When visiting on right subtree first
this.random_traversal(head.right);
process.stdout.write(" " + head.data + " ");
//When visiting on left subtree second
this.random_traversal(head.left);
}
}
}
}
function main()
{
var obj = new BinarySearchTree();
//Add nodes in binary search tree
/*
6
/ \
/ \
3 9
/ \ / \
1 5 7 20
/ /
4 15
*/
obj.add(6);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(5);
obj.add(7);
obj.add(4);
obj.add(15);
obj.random_traversal(obj.root);
process.stdout.write("\n");
obj.random_traversal(obj.root);
process.stdout.write("\n");
obj.random_traversal(obj.root);
process.stdout.write("\n");
obj.random_traversal(obj.root);
}
main();
Output
7 9 15 6 1 3 4 5
15 9 7 6 1 3 4 5
1 3 5 4 6 7 9 15
5 4 3 1 6 15 9 7
# Python 3 Program
# Random traversal in Binary search tree
import random
import sys
# 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 = "")
# Traverse the random nodes in given binary search tree
def random_traversal(self, head) :
if (head != None) :
if (random.randint(0,sys.maxsize-2) % 2 == 0) :
# When visiting on left subtree first
self.random_traversal(head.left)
print(" ", head.data ," ", end = "")
# When visiting on right subtree second
self.random_traversal(head.right)
else :
# When visiting on right subtree first
self.random_traversal(head.right)
print(" ", head.data ," ", end = "")
# When visiting on left subtree second
self.random_traversal(head.left)
def main() :
obj = BinarySearchTree()
# Add nodes in binary search tree
#
# 6
# / \
# / \
# 3 9
# / \ / \
# 1 5 7 20
# / /
# 4 15
#
obj.add(6)
obj.add(3)
obj.add(9)
obj.add(1)
obj.add(5)
obj.add(7)
obj.add(4)
obj.add(15)
obj.random_traversal(obj.root)
print("\n", end = "")
obj.random_traversal(obj.root)
print("\n", end = "")
obj.random_traversal(obj.root)
print("\n", end = "")
obj.random_traversal(obj.root)
if __name__ == "__main__": main()
Output
7 9 15 6 1 3 4 5
1 3 5 4 6 15 9 7
7 9 15 6 4 5 3 1
4 5 3 1 6 15 9 7
#
# Ruby Program
# Random traversal in 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, :rand
attr_accessor :root, :rand
def initialize()
@root = nil
@rand = Random.new
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
# Traverse the random nodes in given binary search tree
def random_traversal(head)
if (head != nil)
if (@rand.rand(0..100) % 2 == 0)
# When visiting on left subtree first
self.random_traversal(head.left)
print(" ", head.data ," ")
# When visiting on right subtree second
self.random_traversal(head.right)
else
# When visiting on right subtree first
self.random_traversal(head.right)
print(" ", head.data ," ")
# When visiting on left subtree second
self.random_traversal(head.left)
end
end
end
end
def main()
obj = BinarySearchTree.new()
# Add nodes in binary search tree
#
# 6
# / \
# / \
# 3 9
# / \ / \
# 1 5 7 20
# / /
# 4 15
#
obj.add(6)
obj.add(3)
obj.add(9)
obj.add(1)
obj.add(5)
obj.add(7)
obj.add(4)
obj.add(15)
obj.random_traversal(obj.root)
print("\n")
obj.random_traversal(obj.root)
print("\n")
obj.random_traversal(obj.root)
print("\n")
obj.random_traversal(obj.root)
end
main()
Output
1 3 5 4 6 15 9 7
7 9 15 6 1 3 4 5
5 4 3 1 6 7 9 15
1 3 4 5 6 7 9 15
/*
Scala Program
Random traversal in Binary search tree
*/
import scala.util.Random;
//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,
var rand: Random)
{
def this()
{
this(null,new Random);
}
//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");
}
}
//Traverse the random nodes in given binary search tree
def random_traversal(head: Node): Unit = {
if (head != null)
{
if (rand.nextInt() % 2 == 0)
{
//When visiting on left subtree first
random_traversal(head.left);
print(" " + head.data + " ");
//When visiting on right subtree second
random_traversal(head.right);
}
else
{
//When visiting on right subtree first
random_traversal(head.right);
print(" " + head.data + " ");
//When visiting on left subtree second
random_traversal(head.left);
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: BinarySearchTree = new BinarySearchTree();
//Add nodes in binary search tree
/*
6
/ \
/ \
3 9
/ \ / \
1 5 7 20
/ /
4 15
*/
obj.add(6);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(5);
obj.add(7);
obj.add(4);
obj.add(15);
obj.random_traversal(obj.root);
print("\n");
obj.random_traversal(obj.root);
print("\n");
obj.random_traversal(obj.root);
print("\n");
obj.random_traversal(obj.root);
}
}
Output
4 5 3 1 6 15 9 7
1 3 4 5 6 15 9 7
5 4 3 1 6 15 9 7
15 9 7 6 4 5 3 1
/*
Swift Program
Random traversal in Binary search tree
*/
import Foundation
#if os(Linux)
srandom(UInt32(time(nil)))
#endif
//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: "");
}
}
//Traverse the random nodes in given binary search tree
func random_traversal(_ head: Node? )
{
if (head != nil)
{
var number = 0;
//Get new rand number
#if os(Linux)
number = Int(random())
#else
number = Int(arc4random_uniform(UInt32(max_value)))
#endif
if (number % 2 == 0)
{
//When visiting on left subtree first
self.random_traversal(head!.left);
print(" ", head!.data ," ", terminator: "");
//When visiting on right subtree second
self.random_traversal(head!.right);
}
else
{
//When visiting on right subtree first
self.random_traversal(head!.right);
print(" ", head!.data ," ", terminator: "");
//When visiting on left subtree second
self.random_traversal(head!.left);
}
}
}
}
func main()
{
let obj: BinarySearchTree = BinarySearchTree();
//Add nodes in binary search tree
/*
6
/ \
/ \
3 9
/ \ / \
1 5 7 20
/ /
4 15
*/
obj.add(6);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(5);
obj.add(7);
obj.add(4);
obj.add(15);
obj.random_traversal(obj.root);
print("\n", terminator: "");
obj.random_traversal(obj.root);
print("\n", terminator: "");
obj.random_traversal(obj.root);
print("\n", terminator: "");
obj.random_traversal(obj.root);
}
main();
Output
7 9 15 6 1 3 4 5
15 9 7 6 1 3 5 4
4 5 3 1 6 7 9 15
15 9 7 6 5 4 3 1
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