Find all leaf node in a binary tree

What are leaf nodes? 

Leaf nodes are those nodes in a tree which have no left and no right child. our problem is to find out all the leaf nodes in a binary tree and store them in a vector.

binary tree

In this figure , the leaf nodes are :

[8 , 9 , 10 , 11 , 13 , 14]

Suppose we have :

Struct TreeNode { Int val ; TreeNode* left ; TreeNode* right; };

Form a new node : 

TreeNode* node = new TreeNode();              // c++ code

Or 

TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); // c code

After applying it to tree , we will check it the node is a leaf node.

To check whether this node is leaf node or not   : 

if(node->left == NULL && node->right == NULL)      // c and c++ code

If it return true , it means `node` is a leaf node else it will other `node`.

How to find all  leaf nodes in a binary tree?

Here we will find all the leaf nodes in a binary tree and store these in a vector. 

Algorithm : 

• Use level order traversal to traverse all the nodes in a binary tree. 

• For every node check the above condition if the node is leaf node or not.

• If it is not a leaf node ,then move forward else push it in the vector.

Code : 

void leaf_nodes(TreeNode* root , vector<TreeNode*> &leafs)     {         queue<TreeNode*>q;         q.push(root);         while(!q.empty())         {              TreeNode* node = q.front();             if(node->left == NULL && node->right == NULL)             {                 leafs.push_back(node);             }             if(node->left)             {                 q.push(node->left);             }             if(node->right)             {                 q.push(node->right);             }             q.pop();         }     }

References : 

https://mycodevillage.blogspot.com/2022/09/429-n-ary-tree-level-order-traversal.html