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
- Create a class
TreeNode
to define the structure of a binary tree node. Each node contains data, a left child, and a right child. - Create a class
BinaryTree
with a root node. This class will have a methodprintPath
that takes anode
and apath
as arguments. - In the
printPath
method, first check if the currentnode
is null. If it is, return, as there is nothing to print. - If the
node
is a leaf node (no left or right child), print thepath
along with thenode
's data. - If the
node
has left and/or right children, recursively callprintPath
on both the left and right children while updating thepath
. - In the
main
function, create an instance of theBinaryTree
class and construct the binary tree. - Call the
printPath
method on the root node with an emptypath
.
Program Solution
-
1) Print all paths from root to leaf using recursion in java
2) Print all paths from root to leaf using recursion in c++
3) Print all paths from root to leaf using recursion in c#
4) Print all paths from root to leaf using recursion in vb.net
5) Print all paths from root to leaf using recursion in php
6) Print all paths from root to leaf using recursion in node js
7) Print all paths from root to leaf using recursion in python
8) Print all paths from root to leaf using recursion in ruby
9) Print all paths from root to leaf using recursion in scala
10) Print all paths from root to leaf using recursion in swift
11) Print all paths from root to leaf using recursion in kotlin
12) Print all paths from root to leaf using recursion in golang
13) Print all paths from root to leaf using recursion in typescript
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.
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.
New Comment