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

All path from root to leaf nodes in binary tree

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.

Program Solution

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.

New Comment