Print all paths in binary search tree

Print all paths in binary search tree

Path to a given node in a tree is list of all nodes from root to that node. A path is complete path if it ends on leaf node. Each leaf node has exactly one path to reach it. Length of path to each leaf varies; maximum length can be N nodes in worst case, in average case it would be logN. Problem is to print all paths of binary search tree.. This problem is closely related or precursor to “Find paths in binary tree with given sum

Consider following tree:
print all paths in BST
All paths is in tree shown are :

10,6,4
10,6,7
10,15,13
10,15,17

To traverse a path, root is always starting point. At each node, call it current node, there are two options, either to go left or right.  Traverse left subtree first till all paths are covered which are on left side of current node, then come back to current node and traverse all paths which are on right side. It is plain traversing of all nodes with some book keeping, to print path when leaf node is visited.

There are two things which are interesting to note. First, each node has to be added and removed from path. Second, node has to be revisited once left subtree is done.

In this case, we add the root node in path and the process each of node on left subtree and then right subtree. What kind of traversal is that? Yes, that’s post order. All we need to do is to replace print statement with actual processing which is to add node to path.

Path can be a global array, which I personally strongly discourage, or an array passed as parameter to function. Also we need to know how many nodes have already been added to path before adding new node to it. Hence another book keeping counter will be passed which tracks number of nodes in path till current node.

Algorithm to print all paths in binary tree

1. Start from root, add node to path
2. Traverse all paths in left subtree
3. Traverse all paths in right subtree
#include<stdio.h>
#include<stdlib.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
 
typedef struct node Node;
 
void printPaths(Node * node, int path[], int pathLen){
 
  	int i;
 
	if(!node)
		return;
 
	path[pathLen]  = node->value;
 
	int isLeaf = ! ( node->left || node->right ) ;
	if(isLeaf ){
		printf("\n Path till node %d is :", node->value);
		for(i=0; i<=pathLen; i++){
			printf("%d, ", path[i]);
		}
	}
 
	printPaths(node->left,  path, pathLen+1);
	printPaths(node->right, path, pathLen+1);
 
	return ;
}
 
Node * createNode(int value){
  Node *newNode =  (Node *)malloc(sizeof(Node));
 
  newNode->value = value;
  newNode->right= NULL;
  newNode->left = NULL;
 
  return newNode;
 
}
 
Node * addNode(Node *node, int value){
  if(!node) return createNode(value);
  
  if (node->value > value)
      node->left = addNode(node->left, value);
  else
      node->right = addNode(node->right, value);

  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;
  int n = 0;
  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  root = addNode(root,37);
  root = addNode(root,45);

  int path[100];
  printPaths(root, path, 0);
 
  return 0;
}

Since we are traversing each node at least once, complexity of this code is O(N).

Let’s take an example and see how program works.
print all paths example

 Adding node 15 to path 
 Path till node 15 is :30, 20, 15, 

 To print all paths on left subtree of node 15
 To print all paths on right subtree of node 15
 To print all paths on right subtree of node 20
Processing node 25
 Adding node 25 to path 
 Path till node 25 is :30, 20, 25, 

 To print all paths on left subtree of node 25
 To print all paths on right subtree of node 25
 To print all paths on right subtree of node 30
Processing node 40
 Adding node 40 to path 
 To print all paths on left subtree of node 40
Processing node 37
 Adding node 37 to path 
 Path till node 37 is :30, 40, 37, 

 To print all paths on left subtree of node 37
 To print all paths on right subtree of node 37
 To print all paths on right subtree of node 40
Processing node 45
 Adding node 45 to path 
 Path till node 45 is :30, 40, 45

Please share if something is wrong or missing. Please share if you think this post helped you.