Print all Root to Leaf paths of a Binary Tree

Given a binary tree, print all the root to leaf paths of the tree.
For example: Consider the tree:
                    1
            2                3
        4        5        6        7

There will be 4 paths to the from root to the leaves 4, 5, 6 and 7 as given in below output:
Output:
1 2 4
1 2 5
1 3 6
1 3 7


Video coming soon!



Subscribe for more updates


Algorithm/Insights

The algorithm traverses the tree in pre-order manner and uses an array list to store the paths.
When a leaf node is reached, the path is printed.
path - an array list that stores the current path.

Step 1: Add root data to the array list.
Step 2: If root is a leaf, print the path and return.
Step 3: Recursively traverse the left subtree.
Step 4: Recursively traverse the right subtree.

Note: A new array list is created in the recursive calls (Steps 3 and 4) because we do not want to share the same array list in left and right subtree calls as the paths will be different.
We add nodes up to the current path to the array list because the paths up to the current node are common for left and right subtrees.


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.saurabh;

import java.util.ArrayList;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Print all Root to Leaf paths of a Binary Tree
 *
 * @author Saurabh
 */
public class RootToLeafPathsTest {
	public static void main(String[] args) {
		Tree tree = new Tree();
		tree.createSampleTree();
		tree.printRootToLeafPaths();
	}
}

class Tree {
	
	private TreeNode root;

	public TreeNode getRoot() {
		return root;
	}

	public void printRootToLeafPaths() {
		if(root == null) {
			return;
		}
		ArrayList<Integer> path = new ArrayList<Integer>();
		printRootToLeafPaths(root, path);
	}

	private void printRootToLeafPaths(TreeNode root, ArrayList<Integer> path) {
		path.add(root.getData());
		
		if(root.getLeft() == null && root.getRight() == null) {
			printList(path);
			return;
		}
		printRootToLeafPaths(root.getLeft(),new ArrayList<Integer>(path));
		printRootToLeafPaths(root.getRight(),new ArrayList<Integer>(path));
	}

	private void printList(ArrayList<Integer> path) {
		for(Integer i: path) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	public void setRoot(TreeNode root) {
		this.root = root;
	}
	
	/*
	 * Create a sample tree
	 * 				1
	 * 		2				3
	 * 4		5		6		7
	 */
	public void createSampleTree() {
		root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));		
	}
}

class TreeNode {

	private int data;
	private TreeNode left;
	private TreeNode right;

	public TreeNode(int data, TreeNode left, TreeNode right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}

	public TreeNode(int i) {
		data = i;
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public TreeNode getLeft() {
		return left;
	}

	public void setLeft(TreeNode left) {
		this.left = left;
	}

	public TreeNode getRight() {
		return right;
	}

	public void setRight(TreeNode right) {
		this.right = right;
	}
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer