Recursive depth-first search for Binary Trees in C
main.c
#include <stdlib.h>
#include <stdio.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
TreeNode* new_node(int val) {
TreeNode* n = malloc(sizeof(TreeNode));
n->val = val;
n->left = NULL;
n->right = NULL;
return n;
}
void print_depth_first(TreeNode* root) {
TreeNode* process_stack[100];
size_t process_stack_num = 0;
process_stack[0] = root;
process_stack_num++;
while (process_stack_num > 0) {
TreeNode* current = process_stack[process_stack_num - 1];
process_stack_num--;
if (current->val == 4) {
printf("%d(yay we found the node 4) ", current->val);
break;
} else {
printf("%d ", current->val);
}
if (current->right != NULL) {
process_stack[process_stack_num] = current->right;
process_stack_num++;
}
if (current->left != NULL) {
process_stack[process_stack_num] = current->left;
process_stack_num++;
}
}
}
int found = 0;
void print_depth_first_recursive(TreeNode* node) {
if (found == 1) {
return;
}
if (node->val == 4) {
printf("%d (yay we found 4) ", node->val);
found = 1;
return;
} else {
printf("%d ", node->val);
}
if (node->left != NULL) {
print_depth_first_recursive(node->left);
}
if (node->right != NULL) {
print_depth_first_recursive(node->right);
}
}
// 0
// / \
// 1 2
// / \ / \
//3 4 5 6
int main(int argc, char* argv[]) {
TreeNode* root = new_node(0);
root->left = new_node(1);
root->right = new_node(2);
root->left->left = new_node(3);
root->left->right = new_node(4);
root->right->left = new_node(5);
root->right->right = new_node(6);
print_depth_first_recursive(root);
return 0;
}
