Root to leaf path – LeetCode Solution [Easy]

Root to leaf path problem statement is:
Given the root of a binary tree, return all root-to-leaf paths in any order.

leaf is a node with no children.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: ["3->9","3->20->15","3->20->7"]

Root to leaf path – Leetcode Solution

Approach

The idea is to use the DFS Traversal of the binary tree to travel from the root to the leaf of the binary tree and store the value of each node.

Pseudocode

// TreeNode structure
struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
}

String s = ""
vector<string> paths

solve (root, paths, s)
  if root == NULL
    return
  //Leaf node reached. Save current path.
  if root->left == NULL && root-right == NULL: 
    paths.push_back(s + root->val)
  solve(root->left, paths, s + root->val + "->");
  solve(root->right, paths, s + root->val + "->");

Code Implementation

//
//  main.cpp
//  Root to leaf path
//
//  Created by Himanshu on 08/02/22.
//

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val = 0;
    struct TreeNode *left, *right;
};

TreeNode* newNode(int data)
{
    TreeNode* Node = new TreeNode();
    Node->val = data;
    Node->left = NULL;
    Node->right = NULL;
 
    return(Node);
}


void solve(TreeNode* root, vector<string>& paths, string s) {
    if (root == NULL) {
        return;
    } else {
        if (root->left == NULL && root->right == NULL) {
            paths.push_back(s + to_string(root->val));
        }
        solve(root->left, paths, s + to_string(root->val) + "->");
        solve(root->right, paths, s + to_string(root->val) + "->");
    }
    
}


int main() {
    TreeNode *root = newNode(3);
    root->left = newNode(9);
    root->right = newNode(20);
    root->right->left = newNode(15);
    root->right->right = newNode(7);
    
    vector<string> paths;
    string s =  "";

    cout<<"Paths from root to leaf are: "<<endl;
    solve(root, paths, s);
    
    for (int i=0; i<paths.size(); i++) {
        cout<<paths[i]<<endl;
    }

    return 0;
}

Here’s a working example:
https://ideone.com/E3ju6P

Leetcode Problem

Leave a Reply