Print paths in a binary tree

We learned various kind of traversals of a binary tree like inorder, preorder and postorder. Paths in a binary tree problem require traversal of a binary tree too like every other problem on a binary tree. The problem statement is:

Given a binary tree, print all paths in that binary tree

What is a path in a binary tree? A path is a collection of nodes from the root to any leaf of the tree. By definition, a leaf node is a node which does not have left or right child. For example, one of the paths in the binary tree below is 10,7,9.

Paths in a binary tree: thoughts

It is clear from the problem statement that we have to start with root and go all the way to leaf nodes. Question is do we need to start with root from each access each path in binary tree? Well, no. Paths have common nodes in them. Once we reach the end of a path (leaf node), we just move upwards one node at a time and explore other paths from the parent node. Once all paths are explored, we go one level again and explore all paths from there. 

This is a typical postorder traversal of a binary tree, we finish the paths in the left subtree of a node before exploring paths on the right subtree We process the root before going into left or right subtree to check if it is the leaf node. We add the current node into the path till now. Once we have explored left and right subtree, the current node is removed from the path.

Let’s take an example and see how does it work. Below is the tree for each we have to print all the paths in it.

First of all our list of paths is empty. We have to create a current path, we start from the root node which is the node(10). Add node(10) to the current path. As node(10) is not a leaf node, we move towards the left subtree.

node(7) is added to the current path. Also, it is not a leaf node either, so we again go down the left subtree.

node(8) is added to the current path and this time, it is a leaf node. We put the entire path into the list of paths or print the entire path based on how we want the output.

At this point, we take outnode(8) from the current path and move up to node(7). As we have traversed the left subtree of,node(7) we will traverse right subtree of the node(7).

node(9) is added now to the current path. It is also a leaf node, so again, put the path in the list of paths. node(9) is moved out of the current path.

Now, left and right subtrees of node(7) have been traversed, we remove node(7) from the current path too.

At this point, we have only one node in the current path which is the node(10) We have already traversed the left subtree of it. So, we will start traversing the right subtree, next we will visit node(15) and add it to the current path.

node(15) is not a leaf node, so we move down the left subtree. node(18) is added to the current path. node(18) is a leaf node too. So, add the entire path to the list of paths. Remove node(18) from the current path.

We go next to the right subtree of the node(15), which is the node(19). It is added to the current path. node(19) is also a leaf node, so the path is added to the list of paths.

Now, the left and right subtrees of the node(15) are traversed, it is removed from the current path and so is the node(10).

Print paths in a binary tree: implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 21.10.18.
 */
public class PrintPathInBST {
    public void printPath(BinarySearchTree tree){
        ArrayList<TreeNode> path  = new ArrayList<>();
        this.printPathRecursive(tree.getRoot(), path);
    }

    private void printPathRecursive(TreeNode root,
									ArrayList<TreeNode> path){
        if(root == null) return;

        path.add(root);

        //If node is leaf node
        if(root.getLeft() == null && root.getRight() == null){
            path.forEach(node -> System.out.print(" " 
							+ node.getValue()));
            path.remove(path.size()-1);
            System.out.println();
            return;
        }

        /*Not a leaf node, add this node to 
		path and continue traverse */
        printPathRecursive(root.getLeft(),path);
        printPathRecursive(root.getRight(), path);

		//Remove the root node from the path
        path.remove(path.size()-1);
    }
}

Test cases

package com.company.BST;
 
/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTreeTests {
    public static void main (String[] args){
        BinarySearchTree binarySearchTree = new BinarySearchTree();
 
        binarySearchTree.insert(7);
        binarySearchTree.insert(8);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);
        binarySearchTree.insert(3);
        binarySearchTree.insert(4);
 
        binarySearchTree.printPath();
    }
}

Tree node definition

package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeNode<T> {
    private T value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public T getValue(){
        return this.value;
    }
    public TreeNode getRight(){
        return this.right;
    }
    public TreeNode getLeft(){
        return this.left;
    }

    public void setValue(T value){
        this.value = value;
    }

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

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

Complexity of above algorithm to print all paths in a binary tree is O(n).

Please share if there is something wrong or missing. If you are preparing for Amazon, Microsoft or Google interviews, please signup for interview material for free.