Binary Tree Paths

Problem Statement: You have been given root of a binary tree. Your task is to return all root-to-leaf paths in any order.

Example:

Input: root = [10, 8, 25, 5, 9, 22]
Output: [10->8->5, 10->8->9, 10->25->22]

Code Implementation:

• Java

import java.util.*;

public class BinaryTreePaths {

// Constructor

static class Node {

int data;

Node left, right;

Node(int key) {

data = key;

left = right = null;

}

}

public static void main(String[] arrgs) {

Node root = new Node(10);

root.left = new Node(8);

root.left.left = new Node(5);

root.left.right = new Node(9);

root.right = new Node(25);

root.right.left = new Node(22);

List<String> paths = new ArrayList<>();

// calling function

getBinaryTreePaths(root, "", paths);

// printing the answer

System.out.println(paths);

}

public static void getBinaryTreePaths(Node root, String ans, List<String> paths) {

// base case

if (root == null)

return;

// if we get leaf node we will add it to our ans

if (root.left == null && root.right == null) {

ans += root.data;

paths.add(ans);

return;

}

// calling left subtree and adding current root value into ans

getBinaryTreePaths(root.left, ans + root.data + "->", paths);

// calling right subtree and adding current root value into ans

getBinaryTreePaths(root.right, ans + root.data + "->", paths);

}

}

Output:

[10->8->5, 10->8->9, 10->25->22]

Complexity Analysis:

Time Complexity: O(n), where n is the number of nodes in tree.

Space Complexity: Considering the stack space, if the tree is balanced then O(log n) and if tree is unbalanced then O(n).