# Leaf Nodes

``````/*
Find the leaf nodes of a tree both iteratively and recursively.

The Algorithm:
- Pretty simple. Simply preorder tranversal, and checking all leafs nodes, which
by definition cannot have any children.
- Iteratively introduces a stack, we are ensuring the add to the right before
we add to the left, and the left node is introduced back before the right.
Which should therefore also follow the convension of a pre-order traversal.
*/

template <class T>
class B_tree {
public:
static void print_leafs(vector<Node<T>*> leafs)
{
for (auto i : leafs)
cout << i->value << endl;
pause();
}

static vector<Node<T>*> leaf_nodes_rec(Node<T> *root)
{
vector<Node<T>*> leafs;
leaf_nodes_rec(root, leafs);
return leafs;
}

static vector<Node<T>*> leaf_nodes_iter(Node<T> *root)
{
vector<Node<T>*> leafs;
if (root == nullptr) leafs;

stack<Node<T>*> s;
s.push(root);

while (!s.empty()) {
Node<T> *temp = s.top();
s.pop();

if (temp->left == nullptr && temp->right == nullptr)
leafs.push_back(temp);

if (temp->right != nullptr)
s.push(temp->right);

if (temp->left != nullptr)
s.push(temp->left);
}

return leafs;
}

private:

static void leaf_nodes_rec(Node<T> *cur_root, vector<Node<T>*> &leafs)
{
if (cur_root != nullptr) {
if (cur_root->left == nullptr && cur_root->right == nullptr) {
leafs.push_back(cur_root);
return;
}
leaf_nodes_rec(cur_root->left, leafs);
leaf_nodes_rec(cur_root->right, leafs);
}
}
};

/*
Tested and Confirmed:
vector<Node<int>*> leafs = B_tree<int>::leaf_nodes_rec(tree->root);
vector<Node<int>*> leafs2 = B_tree<int>::leaf_nodes_iter(tree->root);
B_tree<int>::print_leafs(leafs);
B_tree<int>::print_leafs(leafs2);
*/``````

Last updated