Root to leaf path problem statement is:
Given the root of a binary tree, return all root-to-leaf paths in any order.
A 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;
}
Output
Paths from root to leaf are: 3->9 3->20->15 3->20->7
Here’s a working example: Ideone