Print all paths from Root to leaf.

You are given a binary tree, you need to print all the paths from root to leaf nodes.

In the above figure, the paths from root to leaf are –
8 -> 3 -> 1
8->3->6->4
8->3->6->7
8->10->14->13

Algorithm:

We can solve this problem using backtracking. We keep track of the nodes we have currently visited in a depth first search manner.

  1. Create a vector called path to keep track of the nodes being visited.
  2. If the current node is null, we return.
  3. Else, push the node into the path vector. Check if the node is a leaf node or not. If yes, print all the nodes in the path vector.
  4. Recur for left child and right child of the node. Pop the last node from the path vector for backtracking after left and right subtrees are done.
#include <bits/stdc++.h>

using namespace std;

struct Node{
  Node* left;
  Node* right;
  int data;
};

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}

Node* root = nullptr;

Node* insertNode(Node* node, int key){
    Node* temp = createNode(key);
    if(root == nullptr){
        root = temp;
        return root;
    }
    if(node == nullptr){
        return temp;   
    }
    
    if(key < node->data){
        node->left = insertNode(node->left, key);
    }else if(key > node->data){
        node->right = insertNode(node->right, key);
    }
    return node;
}

void printRootToleafPaths(Node* node, vector<int> &path)
{
    // base case
    if (node == nullptr)
        return;

    // include current node to path vector
    path.push_back(node->data);

    // if leaf node is found, print the path
    if (node->left == nullptr && node->right == nullptr)
    {
        for (int data: path)
            cout << data << " ";
        cout << endl;
    }

    // recur for left and right subtree
    printRootToleafPaths(node->left, path);
    printRootToleafPaths(node->right, path);

    // remove current node after left and right subtree are done
    path.pop_back();
}


void levelOrderTraversal(){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}

int main()
{
    insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 10);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 14);
    insertNode(root, 4);
    insertNode(root, 7);
    insertNode(root, 13);
    cout<<"Level Order traversal => ";
    levelOrderTraversal();
    cout<<endl<<endl;
    vector<int> path;
    cout<<"Root to leaf Paths => ";
    printRootToleafPaths(root, path);
    return 0;
}

Also, check out another popular interview problem Right View of a Binary Tree.

One comment

Leave a Reply

Your email address will not be published.