Skip to content

Fix TreeRandomNode Algorithm #3174

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 8 commits into from
Jul 3, 2022
Merged

Fix TreeRandomNode Algorithm #3174

Changes from all commits
Commits
Show all changes
8 commits
Select commit Hold shift + click to select a range
e6bc253
Fix the folder structure
Ankush263 Jun 14, 2022
8256ae6
Merge branch 'master' into branch1
yanglbme Jun 14, 2022
628a527
fix folder structure
Ankush263 Jun 20, 2022
15e35d5
Merge branch 'branch1' of https://github.com/Ankush263/Java into branch1
Ankush263 Jun 20, 2022
d06e344
Fix TreeRandomNode Algorithm
Ankush263 Jul 3, 2022
f1a1b68
Merge branch 'branch1' of https://github.com/Ankush263/Java into branch1
Ankush263 Jul 3, 2022
3876257
Update TreeRandomNode.java
yanglbme Jul 3, 2022
1739594
Update TreeRandomNode.java
yanglbme Jul 3, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
32 changes: 17 additions & 15 deletions src/main/java/com/thealgorithms/datastructures/trees/TreeRandomNode.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,3 +1,6 @@
package com.thealgorithms.datastructures.trees;


/* Author : Suraj Kumar
Github : https://github.com/skmodi649
*/
Expand All @@ -11,7 +14,7 @@
Step 2: First create a binary tree using the steps mentioned in the first approach
Step 3: Now use a method inOrder() that takes a node as input parameter to traverse through the
binary tree in inorder fashion as also store the values in a ArrayList simultaneously.
Step 4: Now define a method getrandom() that takes a node as input parameter, in this first call
Step 4: Now define a method getRandom() that takes a node as input parameter, in this first call
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.
Step 5: After generating the number display the value of the ArrayList at the generated index
Step 6: STOP
Expand All @@ -21,17 +24,17 @@ the inOrder() method to store the values in the arraylist, then find the size of
import java.util.ArrayList;

// Using auxiliary array to find the random node in a given binary tree
class Node {
int item;
Node left, right;

public Node(int key) {
item = key;
left = right = null;
}
}

public class TreeRandomNode {
private class Node {
int item;
Node left, right;

public Node(int key) {
item = key;
left = right = null;
}
}

// Using an arraylist to store the inorder traversal of the given binary tree
static ArrayList<Integer> list = new ArrayList<>();
Expand All @@ -44,8 +47,9 @@ public class TreeRandomNode {

// Now lets find the inorder traversal of the given binary tree
static void inOrder(Node node) {
if (node == null)
if (node == null) {
return;
}

// traverse the left child
inOrder(node.left);
Expand All @@ -55,15 +59,14 @@ static void inOrder(Node node) {
inOrder(node.right);
}

public void getrandom(Node val)
{
public void getRandom(Node val) {
inOrder(val);
// getting the count of node of the binary tree
int n = list.size();
int min = 0;
int max = n - 1;
//Generate random int value from 0 to n-1
int b = (int)(Math.random()*(max-min+1)+min);
int b = (int) (Math.random() * (max - min + 1) + min);
// displaying the value at the generated index
int random = list.get(b);
System.out.println("Random Node : " + random);
Expand All @@ -90,4 +93,3 @@ from the arraylist using get() method and finally display the result.
/* Time Complexity : O(n)
Auxiliary Space Complexity : O(1)
*/