binary_trees/111-bst_insert.c at master · VicTheM/binary_trees · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include "binary_trees.h"

/**
 * bst_insert_h - Helper Function to insert node into a BST.
 * @tree: Pointer to root node of tree for insertion.
 * @node: Double pointer to node to be inserted in tree.
 * @inserted: Flag to check if node is inserted
 */
void bst_insert_h(bst_t *tree, bst_t **node, int *inserted)
{
	if (!tree)
		return;

	if ((*node)->n > tree->n && !*inserted)
	{
		bst_insert_h(tree->right, node, inserted);
		if (*inserted)
			return;
		tree->right = *node;
		(*node)->parent = tree;
		*inserted = 1;
	}

	else if ((*node)->n < tree->n && !*inserted)
	{
		bst_insert_h(tree->left, node, inserted);
		if (*inserted)
			return;
		tree->left = *node;
		(*node)->parent = tree;
		*inserted = 1;
	}
	else
	{
		*inserted = 1;
		free(*node);
		*node = NULL;
	}
}

/**
 * bst_insert - Function to insert node into a BST.
 * @tree: Double pointer to root node of tree for insertion.
 * @value: Value to be inserted in tree
 * Return: Pointer to created node or NULL on failure.
 */

bst_t *bst_insert(bst_t **tree, int value)
{
	bst_t *node = NULL;
	int inserted = 0;

	if (!tree)
		return (NULL);

	node = binary_tree_node(NULL, value);
	if (!node)
		return (NULL);

	if (!(*tree))
		*tree = node;
	else
		bst_insert_h(*tree, &node, &inserted);

	return (node);
}