Program to Print all the Root to Leaf Paths in the Binary Search Tree

Given a Binary Search Tree (BST), print all paths starting from root to leaf.

Example,

Input

binary search tree

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

bst example diagram 1

Initially the array is empty. Now we perform a depth search traversal on the tree from root node.

bst example diagram 2

First, we visit node 20. Push 20 to the array.

bst example diagram 3

After that, we visit node 10. Push 10 to the array.

bst example diagram 4

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
bst example diagram 5

Since there are no children of node 5. We pop 5 from the array and move back to the previous node.

bst example diagram 6

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
bst example diagram 7

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.

bst example diagram 8

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
bst example diagram 9

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 O(N), 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.

\\*Number\;of\; nodes\; from\; root\; to\; 1st\; leaf = 2\newline\\*Number\;of\; nodes\; from\; root\; to\; 2nd\; leaf = 3\newline\\*Number\;of\; nodes\; from\; root\; to\; 3rd\; leaf = 4\newline\\*.....\newline\\*Number\;of\; nodes\; from\; root\; to\; K-2th\; leaf = K-1\newline\\*Number\;of\; nodes\; from\; root\; to\; K-1th\; leaf = K\newline\\*Number\;of\; nodes\; from\; root\; to\; Kth\; leaf = K+1\newline\\*Total\; Number\; of\; Nodes\; to\; Print = 2 + 3 + 4 + 5 + ... + K + (K+1)  = \dfrac{K*(K+1)}{2}\newline\\*From\; the\; above\; binary\; tree\;, it\; is\; clear\; that\; K = N/2. \newline\\*Substituting\; K\; in\; the\; above\; equation, we\; get\newline\\*Total\; Number\; of\; Nodes\; to\; Print = \dfrac{\dfrac{N}{2}*(\dfrac{N}{2}+1)}{2} \approx N^2\\*\newline

Thus, Time Complexity = O(N^2)

Read

Leave a Comment

Your email address will not be published. Required fields are marked *