**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:

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.

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.

Pingback: Amazon interview experience 3 | Algorithms and Me()

Pingback: Print paths with given sum in binary search tree – Algorithms and Me()

Pingback: Remove all nodes in a binary tree which don’t lie in path – Algorithms and Me()