Print root to leaf paths without using recursion - GeeksforGeeks

Print root to leaf paths without using recursion - GeeksforGeeks
Given a binary tree, print all its root to leaf paths without using recursion. For example, consider the following Binary Tree.

        6
     /    \
    3      5
  /   \     \
 2     5     4
     /   \
    7     4

There are 4 leaves, hence 4 root to leaf paths -
  6->3->2              
  6->3->5->7
  6->3->5->4
  6->5>4

how to extend the traversal to print root to leaf paths? The idea is to maintain a map to store parent pointers of binary tree nodes. Now whenever we encounter a leaf node while doing iterative preorder traversal, we can easily print root to leaf path using parent pointer

/* Function to print root to leaf path for a leaf

   using parent nodes stored in map */

void printTopToBottomPath(Node* curr,

                         map<Node*, Node*> parent)

{

    stack<Node*> stk;

 

    // start from leaf node and keep on pushing

    // nodes into stack till root node is reached

    while (curr)

    {

        stk.push(curr);

        curr = parent[curr];

    }

 

    // Start popping nodes from stack and print them

    while (!stk.empty())

    {

        curr = stk.top();

        stk.pop();

        cout << curr->data << " ";

    }

    cout << endl;

}

 

/* An iterative function to do preorder traversal

   of binary tree  and print root to leaf path

   without using recursion */

void printRootToLeaf(Node* root)

{

    // Corner Case

    if (root == NULL)

        return;

 

    // Create an empty stack and push root to it

    stack<Node*> nodeStack;

    nodeStack.push(root);

 

    // Create a map to store parent pointers of binary

    // tree nodes

    map<Node*, Node*> parent;

 

    // parent of root is NULL

    parent[root] = NULL;

 

    /* Pop all items one by one. Do following for

       every popped item

        a) push its right child and set its parent

           pointer

        b) push its left child and set its parent

           pointer

       Note that right child is pushed first so that

       left is processed first */

    while (!nodeStack.empty())

    {

        // Pop the top item from stack

        Node* current = nodeStack.top();

        nodeStack.pop();

 

        // If leaf node encountered, print Top To

        // Bottom path

        if (!(current->left) && !(current->right))

            printTopToBottomPath(current, parent);

 

        // Push right & left children of the popped node

        // to stack. Also set their parent pointer in

        // the map

        if (current->right)

        {

            parent[current->right] = current;

            nodeStack.push(current->right);

        }

        if (current->left)

        {

            parent[current->left] = current;

            nodeStack.push(current->left);

        }

    }

}

https://www.quora.com/How-do-I-print-all-root-to-leaf-paths-in-binary-tree-iteratively

Read full article from Print root to leaf paths without using recursion - GeeksforGeeks