Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite4fa83b

Browse files
skmodi649github-actionssiriak
authored
Add select random tree node algorithm (TheAlgorithms#2906)
Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>Co-authored-by: Andrii Siriak <siryaka@gmail.com>
1 parent857c4aa commite4fa83b

File tree

2 files changed

+96
-3
lines changed

2 files changed

+96
-3
lines changed

‎DIRECTORY.md‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -133,6 +133,7 @@
133133
*[PrintTopViewofTree](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/PrintTopViewofTree.java)
134134
*[RedBlackBST](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/RedBlackBST.java)
135135
*[SegmentTree](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/SegmentTree.java)
136+
*[TreeRandomNode](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/TreeRandomNode.java)
136137
*[TreeTraversal](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/TreeTraversal.java)
137138
*[TrieImp](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/TrieImp.java)
138139
*[ValidBSTOrNot](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/ValidBSTOrNot.java)
@@ -369,6 +370,7 @@
369370
*[GnomeSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/GnomeSort.java)
370371
*[HeapSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/HeapSort.java)
371372
*[InsertionSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/InsertionSort.java)
373+
*[LinkList Sort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/LinkList_Sort.java)
372374
*[MergeSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/MergeSort.java)
373375
*[MergeSortNoExtraSpace](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/MergeSortNoExtraSpace.java)
374376
*[MergeSortRecursive](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/MergeSortRecursive.java)
@@ -404,14 +406,12 @@
404406
*[Upper](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/strings/Upper.java)
405407
*[WordLadder](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/strings/WordLadder.java)
406408
* test
407-
* java
408-
* com
409-
* thealgorithms
410409
* maths
411410
*[KaprekarNumbersTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/KaprekarNumbersTest.java)
412411
*[PascalTriangleTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PascalTriangleTest.java)
413412
*[PronicNumberTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PronicNumberTest.java)
414413
* others
415414
*[ArrayLeftRotationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/ArrayLeftRotationTest.java)
415+
*[LinkList Sort test](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/LinkList_Sort_test.java)
416416
* searches
417417
*[QuickSelectTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/QuickSelectTest.java)
Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
/* Author : Suraj Kumar
2+
Github : https://github.com/skmodi649
3+
*/
4+
5+
/* PROBLEM DESCRIPTION :
6+
There is a Binary Search Tree given, and we are supposed to find a random node in the given binary tree.
7+
*/
8+
9+
/* ALGORITHM :
10+
Step 1: START
11+
Step 2: First create a binary tree using the steps mentioned in the first approach
12+
Step 3: Now use a method inOrder() that takes a node as input parameter to traverse through the
13+
binary tree in inorder fashion as also store the values in a ArrayList simultaneously.
14+
Step 4: Now define a method getrandom() that takes a node as input parameter, in this first call
15+
the inOrder() method to store the values in the arraylist, then find the size of the binary tree and now just generate a random number between 0 to n-1.
16+
Step 5: After generating the number display the value of the ArrayList at the generated index
17+
Step 6: STOP
18+
*/
19+
20+
21+
importjava.util.ArrayList;
22+
23+
// Using auxiliary array to find the random node in a given binary tree
24+
classNode {
25+
intitem;
26+
Nodeleft,right;
27+
28+
publicNode(intkey) {
29+
item =key;
30+
left =right =null;
31+
}
32+
}
33+
34+
publicclassTreeRandomNode {
35+
36+
// Using an arraylist to store the inorder traversal of the given binary tree
37+
staticArrayList<Integer>list =newArrayList<>();
38+
// root of Tree
39+
Noderoot;
40+
41+
TreeRandomNode() {
42+
root =null;
43+
}
44+
45+
// Now lets find the inorder traversal of the given binary tree
46+
staticvoidinOrder(Nodenode) {
47+
if (node ==null)
48+
return;
49+
50+
// traverse the left child
51+
inOrder(node.left);
52+
53+
list.add(node.item);
54+
// traverse the right child
55+
inOrder(node.right);
56+
}
57+
58+
publicvoidgetrandom(Nodeval)
59+
{
60+
inOrder(val);
61+
// getting the count of node of the binary tree
62+
intn =list.size();
63+
intmin =0;
64+
intmax =n -1;
65+
//Generate random int value from 0 to n-1
66+
intb = (int)(Math.random()*(max-min+1)+min);
67+
// displaying the value at the generated index
68+
intrandom =list.get(b);
69+
System.out.println("Random Node : " +random);
70+
71+
}
72+
}
73+
74+
75+
/* Explanation of the Approach :
76+
(a) Form the required binary tree
77+
(b) Now use the inOrder() method to get the nodes in inOrder fashion and also store them in the given arraylist 'list'
78+
(c) Using the getRandom() method generate a random number between 0 to n-1, then get the value at the generated random number
79+
from the arraylist using get() method and finally display the result.
80+
*/
81+
82+
83+
/* OUTPUT :
84+
First output :
85+
Random Node : 15
86+
Second output :
87+
Random Node : 99
88+
*/
89+
90+
/* Time Complexity : O(n)
91+
Auxiliary Space Complexity : O(1)
92+
*/
93+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp