Given a Binary Search Tree (BST), print all paths starting from root to leaf.
Example,
Input
Output
20 -> 10 -> 5
20 -> 10 -> 15
20 -> 30 -> 25
20 -> 30 -> 35
Algorithm
The question is very simple. If you look carefully at the output of the above example, you will notice that the output is a depth-first search traversal of the input binary search tree. When we encounter a leaf node, we simply print all the nodes we have visited to reach that leaf node.
To keep track of which path we took to reach the current leaf node, we use an array. Whenever we visit a node, we push the node to the array. After visiting all the paths that go through a node, we remove that node from the array.
Step by Step Example
Let the input binary tree be
Initially the array is empty. Now we perform a depth search traversal on the tree from root node.
First, we visit node 20. Push 20 to the array.
After that, we visit node 10. Push 10 to the array.
After that, we visit node 5. Push 5 to the array. Since node 5 is a leaf node, we print the content of the array.
Output 20 -> 10 -> 5
Since there are no children of node 5. We pop 5 from the array and move back to the previous node.
Now we visit node 15. Push 15 to the array. Since node 15 is a leaf node, we print the content of the array.
Output 20 -> 10 -> 15
There are no children of the node 15, thus we pop 15 from the array and go back to node 10. All the children of node 10 are visited, thus we pop 10 from the array and go back to node 20.
After that, we visit node 30 and push 30 to the array. Then we visit node 25 and push 25 to the array. Since node 25 is a leaf node, we print the content of the array.
Output 20 -> 30 -> 25
There are no children of the node 25, thus we simply pop 25 from the array and go back to node 30. After that, we visit other children of node 30 that is node 35. We push 35 to the array. Since 35 is a leaf node, we print the content of the array.
Output 20 -> 30 -> 35
In this way, we print all the paths from root to leaf nodes in a binary tree.
Program to Print all the Root to Leaf Paths in a Binary Tree
#include <stdio.h>
#include <stdlib.h>
struct node {
int d;
struct node* left;
struct node* right;
};
// function to insert data to binary search tree
struct node* InsertInBST(struct node* root, int data) {
if (root == NULL) {
struct node* temp = (struct node*) malloc(sizeof(struct node));
temp->d = data;
temp->left = temp->right = NULL;
return temp;
}
if (root->d >= data) {
root->left = InsertInBST(root->left, data);
}
else {
root->right = InsertInBST(root->right, data);
}
return root;
}
// function to print all paths from root to leaf nodes
// using depth first search algorithm
void PrintPathsDFS(struct node* root, int* a, int x) {
int i;
// add the current node to the temporary array
a[x] = root->d;
++x;
// if the node is a leaf node, print the content of the array
// the array contains the path from root to this leaf node
if (root->left == NULL && root->right == NULL) {
for (i = 0; i < x - 1; ++i) {
printf("%d -> ", a[i]);
}
printf("%d\n", a[x - 1]);
}
if (root->left != NULL) {
PrintPathsDFS(root->left, a, x);
}
if (root->left != NULL) {
PrintPathsDFS(root->right, a, x);
}
}
int main() {
// temporary array to store path from root to leaf
int a[100000];
node* root;
root = NULL;
/* Input binary search tree is
20
/ \
10 30
/ \ / \
5 15 25 35
*/
root = InsertInBST(root, 20);
root = InsertInBST(root, 10);
root = InsertInBST(root, 5);
root = InsertInBST(root, 15);
root = InsertInBST(root, 30);
root = InsertInBST(root, 25);
root = InsertInBST(root, 35);
PrintPathsDFS(root, a, 0);
}
Output
20 -> 10 -> 5 20 -> 10 -> 15 20 -> 30 -> 25 20 -> 30 -> 35
Time Complexity
At first glance, you may say that the time complexity of the above algorithm is 
, where N is the number of nodes but this is not the case. For each leaf node, we are printing path from root to leaf node. We also need to consider the time to print paths. Suppose we have a binary search tree of N nodes such that every right node is a leaf node as shown below. Let K be the number of leaf nodes.
Thus, Time Complexity = O(N^2)
Read
- Level Order Traversal of Binary Tree
- Right Shift Array by One ( 3 Methods )
- Find Square Root of a Number using Binary Search
- Reverse Linked List in Group