Practice › Trees
Root to Leaf Paths
Medium · Trees · Asked at Amazon, Google, Microsoft, Apple
Print every path from the root to a leaf, one per line, written as values joined by ->. Print the paths in left-to-right order of their leaves.
Input
First line: k. Second line: k values — the tree in level order, -1 means no node.
Output
One path per line.
Constraints
- 1 ≤ number of nodes ≤ 1000
DFS with the current path; at a leaf, print it. Visit the left child before the right child.
Example 1
Input
5 1 2 3 -1 5
Output
1->2->5 1->3
Example 2
Input
1 1
Output
1
Hints
- Carry the path from the root down in a DFS.
- At a leaf, print the current path; then backtrack. Visiting the left child first gives left-to-right order.
Approach
DFS with a list path: push the node's value, and if the node is a leaf, output the path joined with "->". Otherwise recurse into the left child, then the right child. Pop the value when returning so the list always describes the current root-to-node path.
Complexity: O(n · h) time (printing paths) · O(h) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *left = nullptr, *right = nullptr;
Node(long long v) : val(v) {}
};
// Build a tree from level order where -1 means "no node".
Node *readTree() {
int k;
cin >> k;
vector<long long> v(k);
for (auto &x : v) cin >> x;
if (k == 0 || v[0] == -1) return nullptr;
Node *root = new Node(v[0]);
queue<Node *> q;
q.push(root);
int i = 1;
while (!q.empty() && i < k) {
Node *cur = q.front();
q.pop();
if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
i++;
}
return root;
}
vector<long long> path;
void dfs(Node *n) {
if (!n) return;
path.push_back(n->val);
if (!n->left && !n->right) {
for (size_t i = 0; i < path.size(); i++) cout << (i ? "->" : "") << path[i];
cout << "\n";
}
dfs(n->left);
dfs(n->right);
path.pop_back();
}
int main() {
dfs(readTree());
return 0;
}Python solution
import sys
from collections import deque
sys.setrecursionlimit(100000)
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def build_tree(v):
"""Build a tree from level order where -1 means "no node"."""
if not v or v[0] == -1:
return None
root = Node(v[0])
q, i = deque([root]), 1
while q and i < len(v):
cur = q.popleft()
if i < len(v) and v[i] != -1:
cur.left = Node(v[i])
q.append(cur.left)
i += 1
if i < len(v) and v[i] != -1:
cur.right = Node(v[i])
q.append(cur.right)
i += 1
return root
data = list(map(int, sys.stdin.read().split()))
k = data[0]
root = build_tree(data[1 : 1 + k])
rest = data[1 + k :]
out, path = [], []
def dfs(n):
if not n:
return
path.append(str(n.val))
if not n.left and not n.right:
out.append("->".join(path))
dfs(n.left)
dfs(n.right)
path.pop()
dfs(root)
print("\n".join(out))Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node left, right;
Node(long v) { val = v; }
}
// Build a tree from level order where -1 means "no node".
static Node readTree(Scanner sc) {
int k = sc.nextInt();
long[] v = new long[k];
for (int i = 0; i < k; i++) v[i] = sc.nextLong();
if (k == 0 || v[0] == -1) return null;
Node root = new Node(v[0]);
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < k) {
Node cur = q.poll();
if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
i++;
}
return root;
}
static List<Long> path = new ArrayList<>();
static StringBuilder sb = new StringBuilder();
static void dfs(Node n) {
if (n == null) return;
path.add(n.val);
if (n.left == null && n.right == null) {
for (int i = 0; i < path.size(); i++) sb.append(i > 0 ? "->" : "").append(path.get(i));
sb.append('\n');
}
dfs(n.left);
dfs(n.right);
path.remove(path.size() - 1);
}
public static void main(String[] args) {
dfs(readTree(new Scanner(System.in)));
System.out.print(sb);
}
}