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