<p>Given the <code>root</code> of a binary tree, return <em>all root-to-leaf paths in <strong>any order</strong></em>.</p>

<p>A <strong>leaf</strong> is a node with no children.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/12/paths-tree.jpg" style="width: 207px; height: 293px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,null,5]
<strong>Output:</strong> [&quot;1-&gt;2-&gt;5&quot;,&quot;1-&gt;3&quot;]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> root = [1]
<strong>Output:</strong> [&quot;1&quot;]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 100]</code>.</li>
	<li><code>-100 &lt;= Node.val &lt;= 100</code></li>
</ul>

//Approach1 : Recursion
//
//                  rootNode
//                     |
//                     V
//Flow diagram : binaryTreePaths
//                     |
//                     V
//              call dfs with rootNode
//                            path = ""
//                            binaryTreePath empty list
//                     |
//                     V
//                 return binaryTreePath
//
//    currNode, path, binaryTreePath
//                |
//                V
//Flow diagram : dfs
//                |
//                v                  Yes
//           if currNode is nullptr--------> return
//                |No
//                V                  Yes
//          if currNode is leafNode-------->add path to binaryTreePath---->return
//                |No
//                V
//          path = path + "->"
//                |
//                V
//         call dfs with currNode->left,
//                                 path,
//                                 binaryTreePath
//         call dfs with currNode->right,
//                                  path,
//                                  binaryTreePath
//                |
//                V
//              return
//Note : we can call dfs with left or right in any order 
/*
class Solution
{
public:
    vector<string> binaryTreePaths(TreeNode* rootNode)
    {
        string path = "";
        vector<string> binaryTreePath;

        dfs(rootNode, path, binaryTreePath);

        return binaryTreePath;
    }

    void dfs(TreeNode* currNode, string path, vector<string>& binaryTreePath)
    {
        if(currNode)
        {
            path = path + to_string(currNode->val);

            if(!currNode->left && !currNode->right)
            {
                binaryTreePath.push_back(path);
            }
            else
            {
                path = path + "->";
                dfs( currNode->right, path, binaryTreePath );
                dfs( currNode->left, path, binaryTreePath );

            }
        }
    }
};
*/
//Complexity Analysis
//Time complexity: O(NlogN)
//                 Visit each node exactly once
//                 and for each node cost of copying paths will be logn - logn is height of tree
//Space complexity: O(N)
//                  List to store the answer. 
//                   Paths contains as many elements as leaves in the tree and hence could not be 
//                   larger than logN for the trees containing more than one element
//                            + 
//                  Recursion stack taking space
//                  Hence the space complexity is determined by a stack call. 
//                  O(N) : In worst case, when the tree is completely unbalanced,
//                         e.g. each node has only one child node, 
//                              the recursion call would occur N times (the height of the tree)
//                 O(logN) in best case : Tree is balanced - height is log(N)                   
//-------------------------------------------------------------------------------
//Approach 2: Iterations
//
//                 rootNode
//                     |
//                     V
//Flow diagram : binaryTreePaths
//                     |
//                     V                   Yes
//                if rootNode is nullptr---------> return empty vector<string>
//                     |No
//                     V
//              push rootNode to nodesQueue 
//              push rootNode->val to pathsQueue
//                     |
//                     V
//             while nodesQueue is not empty<------------------------------------------.
//             | for current queuesize iterate<------------------------------------.   |
//             | | pop into currNode from nodesQueue                               |   |
//             | | pop into currPath from pathsQueue                               |   |
//             | |  |                                                              |   |  
//             | |  V                         Yes                                  |   |
//             | | if currNode is leaf node----------> push currPath               |   |
//             | |  |                                  to binaryTreePath---------->'   |
//             | |  |No                                                            ^   |
//             | |  V                                   Yes                        |   |
//             | | check if currNode->left is nullptr-----------------------.      |   |
//             | |  |No                                                     |      |   |
//             | |  V                                                       |      |   |
//             | | push currNode->left to nodesQueue                        |      |   |
//             | | push path + "->" + currNode->val to pathsQueue           |      |   |
//             | | |                                                        V      |   |
//             | | '--------------------------------------------------------'      |   |
//             | |                            |                                    |   |
//             | |                            V                                    |   |
//             | | check if currNode->right is nullptr----------------------.      |   |
//             | |  |No                                                     |      |   |
//             | |  V                                                       |      |   |
//             | | push currNode->right to nodesQueue                       |      |   |
//             | | push path + "->" + currNode->val to pathsQueue           |      |   |
//             | | |                                                        V      |   |
//             | | '--------------------------------------------------------'      |   |
//             | |                           |                                     |   |
//             | |                           V                                     |   |
//             | '-----------------------------------------------------------------'   |
//             '-----------------------------------------------------------------------'
class Solution
{
public:
    vector<string> binaryTreePaths(TreeNode* rootNode)
    {
        vector<string> binaryTreePath;

        if (!rootNode)
        {
            return binaryTreePath;
        }

        queue<TreeNode*> nodesQueue;
        nodesQueue.push(rootNode);

        queue<string> paths;
        paths.push( to_string(rootNode->val) );

        while ( !nodesQueue.empty() )
        {
            int qSize = nodesQueue.size();

            while (qSize--)
            {
                //get and pop node
                TreeNode* currNode = nodesQueue.front();
                nodesQueue.pop();

                string path = paths.front();
                paths.pop();

                if (!currNode->left && !currNode->right)
                {
                    binaryTreePath.push_back(path);
                    continue;
                }

                if( currNode->left )
                {
                    nodesQueue.push({currNode->left});
                    paths.push(path + "->" + to_string(currNode->left->val));
                }

                if( currNode->right )
                {
                    nodesQueue.push({currNode->right});
                    paths.push(path + "->" + to_string(currNode->right->val));
                }
            }
        }

        return binaryTreePath;
    }
};
//Complexity Analysis
// Time complexity: O(N) since each node is visited exactly once.
//Space complexity: O(N) as we could keep up to the entire tree.
15800