Posted on by Kalkicode
Code Recursion

# Efficiently print all paths in binary tree using recursion

In this problem, we aim to efficiently print all paths from the root to leaf nodes in a binary tree using recursion. We need to design a program that traverses the binary tree and prints the paths in an organized manner.

## Problem Statement

Given a binary tree, our goal is to print all possible paths from the root node to each leaf node. The paths should be displayed as sequences of nodes.

## Example Scenario

Consider the binary tree shown in the diagram, where numbers in the nodes represent node values. We want to print all paths from the root to each leaf node.

``````
1
/ \
/   \
5     7
/ \   / \
2   4 9   3
/       \
6         8``````

The expected output for this example would be:

``````1 5 2
1 5 4 6
1 7 9
1 7 3 8``````

## Idea to Solve the Problem We can solve this problem using a recursive approach. During the traversal of the binary tree, we keep track of the current path from the root to the current node. When we reach a leaf node, we print the entire path. We recursively visit the left and right subtrees while updating the path accordingly.

## Pseudocode

``````class BinaryTree:
void printPath(node, path):
if node is null:
return
else if node has no left or right child:
print path + " " + node.data
else:
printPath(node.left, path + " " + node.data)
printPath(node.right, path + " " + node.data)

main:
tree = new BinaryTree()
# Construct the binary tree
# ...

# Call the printPath method on the root node
tree.printPath(tree.root, "")``````

## Algorithm Explanation

1. Create a class `TreeNode` to define the structure of a binary tree node. Each node contains data, a left child, and a right child.
2. Create a class `BinaryTree` with a root node. This class will have a method `printPath` that takes a `node` and a `path` as arguments.
3. In the `printPath` method, first check if the current `node` is null. If it is, return, as there is nothing to print.
4. If the `node` is a leaf node (no left or right child), print the `path` along with the `node`'s data.
5. If the `node` has left and/or right children, recursively call `printPath` on both the left and right children while updating the `path`.
6. In the `main` function, create an instance of the `BinaryTree` class and construct the binary tree.
7. Call the `printPath` method on the root node with an empty `path`.

## Output Explanation

The code efficiently prints all paths from the root to leaf nodes in the binary tree. The output demonstrates the paths in the order they are traversed.

## Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because each node is visited exactly once during the traversal.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post