Skip to content

Commit 69729b4

Browse files
mursalfkmursalfk
authored
Merge branch 'main' into main
2 parents 23ae8b5 + ae2276e commit 69729b4

4 files changed

Lines changed: 226 additions & 2 deletions

File tree

‎Rust/DFSGraph.rs‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -84,5 +84,4 @@ fn main() {
8484

8585
let start_node = 0;
8686
println!("Starting DFS from node {}", start_node);
87-
dfs(&graph, start_node);
88-
}
87+
dfs(&graph, start_node);

‎Rust/InorderTraversal.rs‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
// A node in the binary tree.
2+
struct Node {
3+
value: i32,
4+
// We use Option<Box<Node>> to allow for nullable, heap-allocated children.
5+
// Box<T> allows us to have a recursive type with a known size.
6+
left: Option<Box<Node>>,
7+
right: Option<Box<Node>>,
8+
}
9+
10+
// A simple representation of the tree itself.
11+
struct BinaryTree {
12+
root: Option<Box<Node>>,
13+
}
14+
15+
16+
/// A recursive helper function to perform the in-order traversal.
17+
fn in_order_recursive(node: &Option<Box<Node>>, result: &mut Vec<i32>) {
18+
// Check if the current node exists.
19+
if let Some(current_node) = node {
20+
// 1. Traverse the left subtree.
21+
in_order_recursive(&current_node.left, result);
22+
23+
// 2. Visit the root node.
24+
result.push(current_node.value);
25+
26+
// 3. Traverse the right subtree.
27+
in_order_recursive(&current_node.right, result);
28+
}
29+
}
30+
31+
/// The public function to start the in-order traversal.
32+
pub fn in_order_traversal(tree: &BinaryTree) -> Vec<i32> {
33+
let mut result = Vec::new();
34+
in_order_recursive(&tree.root, &mut result);
35+
result
36+
}
37+
38+
39+
fn main() {
40+
// Manually construct a sample binary tree.
41+
// 4
42+
// / \
43+
// 2 5
44+
// / \
45+
// 1 3
46+
let tree = BinaryTree {
47+
root: Some(Box::new(Node {
48+
value: 4,
49+
left: Some(Box::new(Node {
50+
value: 2,
51+
left: Some(Box::new(Node {
52+
value: 1,
53+
left: None,
54+
right: None,
55+
})),
56+
right: Some(Box::new(Node {
57+
value: 3,
58+
left: None,
59+
right: None,
60+
})),
61+
})),
62+
right: Some(Box::new(Node {
63+
value: 5,
64+
left: None,
65+
right: None,
66+
})),
67+
})),
68+
};
69+
70+
let traversal_result = in_order_traversal(&tree);
71+
72+
println!("In-order traversal result: {:?}", traversal_result);
73+
}

‎Rust/PostOrderTraversal.rs‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
// ## The Data Structures ##
2+
3+
// A node in the binary tree.
4+
struct Node {
5+
value: i32,
6+
// Option<Box<Node>> allows for nullable, heap-allocated children.
7+
left: Option<Box<Node>>,
8+
right: Option<Box<Node>>,
9+
}
10+
11+
// Represents the tree itself.
12+
struct BinaryTree {
13+
root: Option<Box<Node>>,
14+
}
15+
16+
// ## Implementation ##
17+
18+
/// A recursive helper function for the post-order traversal.
19+
fn post_order_recursive(node: &Option<Box<Node>>, result: &mut Vec<i32>) {
20+
// Check if the current node exists.
21+
if let Some(current_node) = node {
22+
// 1. Traverse the left subtree.
23+
post_order_recursive(&current_node.left, result);
24+
25+
// 2. Traverse the right subtree.
26+
post_order_recursive(&current_node.right, result);
27+
28+
// 3. Visit the root node last.
29+
result.push(current_node.value);
30+
}
31+
}
32+
33+
/// The public function to start the post-order traversal.
34+
pub fn post_order_traversal(tree: &BinaryTree) -> Vec<i32> {
35+
let mut result = Vec::new();
36+
post_order_recursive(&tree.root, &mut result);
37+
result
38+
}
39+
40+
// ## Putting It All Together ##
41+
42+
fn main() {
43+
// Manually construct a sample binary tree.
44+
// 4
45+
// / \
46+
// 2 5
47+
// / \
48+
// 1 3
49+
let tree = BinaryTree {
50+
root: Some(Box::new(Node {
51+
value: 4,
52+
left: Some(Box::new(Node {
53+
value: 2,
54+
left: Some(Box::new(Node {
55+
value: 1,
56+
left: None,
57+
right: None,
58+
})),
59+
right: Some(Box::new(Node {
60+
value: 3,
61+
left: None,
62+
right: None,
63+
})),
64+
})),
65+
right: Some(Box::new(Node {
66+
value: 5,
67+
left: None,
68+
right: None,
69+
})),
70+
})),
71+
};
72+
73+
let traversal_result = post_order_traversal(&tree);
74+
75+
println!("Post-order traversal result: {:?}", traversal_result);
76+
}

‎Rust/PreOrderTraversal.ts‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
// ## The Data Structures ##
2+
3+
// A node in the binary tree.
4+
struct Node {
5+
value: i32,
6+
// Option<Box<Node>> allows for nullable, heap-allocated children.
7+
left: Option<Box<Node>>,
8+
right: Option<Box<Node>>,
9+
}
10+
11+
// Represents the tree itself.
12+
struct BinaryTree {
13+
root: Option<Box<Node>>,
14+
}
15+
16+
// ## Implementation ##
17+
18+
/// A recursive helper function for the pre-order traversal.
19+
fn pre_order_recursive(node: &Option<Box<Node>>, result: &mut Vec<i32>) {
20+
// Check if the current node exists.
21+
if let Some(current_node) = node {
22+
// 1. Visit the root node first.
23+
result.push(current_node.value);
24+
25+
// 2. Traverse the left subtree.
26+
pre_order_recursive(&current_node.left, result);
27+
28+
// 3. Traverse the right subtree.
29+
pre_order_recursive(&current_node.right, result);
30+
}
31+
}
32+
33+
/// The public function to start the pre-order traversal.
34+
pub fn pre_order_traversal(tree: &BinaryTree) -> Vec<i32> {
35+
let mut result = Vec::new();
36+
pre_order_recursive(&tree.root, &mut result);
37+
result
38+
}
39+
40+
// ## Putting It All Together ##
41+
42+
fn main() {
43+
// Manually construct a sample binary tree.
44+
// 4
45+
// / \
46+
// 2 5
47+
// / \
48+
// 1 3
49+
let tree = BinaryTree {
50+
root: Some(Box::new(Node {
51+
value: 4,
52+
left: Some(Box::new(Node {
53+
value: 2,
54+
left: Some(Box::new(Node {
55+
value: 1,
56+
left: None,
57+
right: None,
58+
})),
59+
right: Some(Box::new(Node {
60+
value: 3,
61+
left: None,
62+
right: None,
63+
})),
64+
})),
65+
right: Some(Box::new(Node {
66+
value: 5,
67+
left: None,
68+
right: None,
69+
})),
70+
})),
71+
};
72+
73+
let traversal_result = pre_order_traversal(&tree);
74+
75+
println!("Pre-order traversal result: {:?}", traversal_result);
76+
}

0 commit comments

Comments
 (0)