Posted on by Kalkicode
Code Stack

# Print all paths from leaf node to root

In this problem, we are given a binary tree, and our task is to print all the paths from each leaf node to the root node. A path is a sequence of nodes from a leaf node to the root node, and it represents a unique path in the binary tree. We need to traverse the binary tree and collect the nodes along the path from the leaf node to the root node using a stack, and then print the collected nodes in reverse order to display the path.

## Problem Statement

Given a binary tree, print all the paths from each leaf node to the root node.

## Example

Consider the following binary tree:

``````
1
/ \
2   3
/   / \
4   5   6
/ \     /
-1   7   8
/ \
9   10
``````

The paths from each leaf node to the root node are:

1. Path from leaf node -1 to root node 1: [-1, 4, 2, 1]
2. Path from leaf node 7 to root node 1: [7, 4, 2, 1]
3. Path from leaf node 5 to root node 1: [5, 3, 1]
4. Path from leaf node 9 to root node 1: [9, 8, 6, 3, 1]
5. Path from leaf node 10 to root node 1: [10, 8, 6, 3, 1]

## Idea to Solve

To print all paths from each leaf node to the root node, we can use a recursive approach with a stack to collect the nodes along the path. We traverse the binary tree and push each node onto the stack as we move down the tree. When we reach a leaf node, we print the nodes in the stack in reverse order to get the path from the leaf to the root. After printing the path, we pop the leaf node from the stack and continue the traversal.

## Algorithm

1. Create a class `Node` to represent the binary tree node with `data`, `left`, and `right` pointers.
2. Create a class `MyStack` to represent the custom stack with `element` (of type `Node`) and `next` (to point to the next stack element).
3. Create a class `BinaryTree` with `top` (of type `MyStack`) and `root` (of type `Node`) representing the binary tree.
4. Implement the `push` method in `MyStack` to add an element to the top of the stack.
5. Implement the `pop` method in `MyStack` to remove the top element from the stack.
6. Implement the `print_path` method in `BinaryTree` to print the path from leaf to root by traversing the stack and printing the elements in reverse order.
7. Implement the `show_path` method in `BinaryTree` to collect the path using the stack and print the paths from leaf to root by calling `print_path` when a leaf node is encountered.
8. In the `main` method, create the binary tree and call `show_path` to print all the paths from each leaf node to the root node.

## Code Solution

``````/*
C Program
Print all paths from leaf node to root
*/
#include <stdio.h>

#include <stdlib.h>

//Structure of Binary Node
struct Node
{
int data;
struct Node *left, *right;
};
//Define the custom stack structure
struct MyStack
{
//First is element of Binary tree node
struct Node *element;
//Second are used to hold information of next node
struct MyStack *next;
};
//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes
struct Node *insert(int data)
{
//create dynamic memory to new binary tree node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-child is NULL
new_node->right = NULL; //Initially node right-child is NULL
}
else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
//return reference
return new_node;
}
//Create a new stack element and return this newly node
struct MyStack *push(struct Node *tree_node, struct MyStack *head)
{
//Create new node of Stack
struct MyStack *node = (struct MyStack *) malloc(sizeof(struct MyStack));
if (node != NULL)
{
//Set tree node
node->element = tree_node;
//Connect new node into head of Stack
}
else
{
printf("Memory Overflow\n");
//Terminate program execution
exit(0);
}
return node;
}
//Remove a top element of stack
void pop(struct MyStack **top)
{
if ( *top != NULL)
{
struct MyStack *remove = *top;
//Visit to next top element
*top = remove->next;
//set remove node values
remove->element = NULL;
remove->next = NULL;
//free node memory
free(remove);
remove = NULL;
}
}
//Function which is display the path from leaf to root
void print_path(struct MyStack *temp)
{
if (temp != NULL)
{
printf("  %d  ", temp->element->data);
print_path(temp->next);
}
}
//This function are collect path information using stack and when get leaf node then displaying node value
void show_path(struct Node *root, struct MyStack **head)
{
if (root != NULL)
{
//Add a new element into Stack
if (root->left == NULL && root->right == NULL)
{
//when get leaf node then display path
printf("\n[");
printf(" ]\n");
}
}
}
int main()
{
struct Node *root = NULL;
/*Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
/  \      /
-1    7    8
/ \
9   10
*/
//Insert node into Binary tree
root = insert(1);
root->left = insert(2);
root->right = insert(3);
root->right->right = insert(6);
root->right->left = insert(5);
root->left->left = insert(4);
root->left->left->left = insert(-1);
root->left->left->right = insert(7);
root->right->right->left = insert(8);
root->right->right->left->left = insert(9);
root->right->right->left->right = insert(10);
struct MyStack *head = NULL;
//Display leaf to all root path
//bottom up
return 0;
}``````

#### Output

``````[  -1    4    2    1   ]

[  7    4    2    1   ]

[  5    3    1   ]

[  9    8    6    3    1   ]

[  10    8    6    3    1   ]``````
``````/*
Java Program
Print all paths from leaf node to root
*/
//Tree node
class Node
{
public int data;
public Node left;
public Node right;
//Set initial value of Binary Tree Node
public Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
//Define the custom stack class
class MyStack
{
public Node element;
public MyStack next;
public MyStack(Node element)
{
this.element = element;
this.next = null;
}
}
class BinaryTree
{
public MyStack top;
public Node root;
public BinaryTree()
{
this.top = null;
this.root = null;
}
//add element into top of stack
public void push(Node element)
{
MyStack new_node = new MyStack(element);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
}
//Remove top element
public void pop()
{
if (this.top == null)
{
return;
}
MyStack temp = this.top;
this.top = temp.next;
temp = null;
}
//Function which is display the path from leaf to root
public void print_path(MyStack temp)
{
if (temp != null)
{
System.out.print(" " + temp.element.data + " ");
print_path(temp.next);
}
}
//This function are collect path information using stack and when get leaf node then displaying node value
public void show_path(Node root)
{
if (root != null)
{
//Add a new element into Stack
this.push(root);
this.show_path(root.left);
this.show_path(root.right);
if (root.left == null && root.right == null)
{
System.out.print("\n[");
this.print_path(this.top);
System.out.print(" ]\n");
}
this.pop();
}
}
public static void main(String[] args)
{
BinaryTree obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
/ \       /
-1   7     8
/ \
9   10
*/
//Insert node into Binary tree
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.left = new Node(-1);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);
obj.root.right.right.left.left = new Node(9);
obj.root.right.right.left.right = new Node(10);
//Display all path between leaf to root
obj.show_path(obj.root);
}
}``````

#### Output

``````[ -1  4  2  1  ]

[ 7  4  2  1  ]

[ 5  3  1  ]

[ 9  8  6  3  1  ]

[ 10  8  6  3  1  ]``````
``````/*
C++ Program
Print all paths from leaf node to root
*/

#include<iostream>
using namespace std;

//Tree node
class Node
{
public:
int data;
Node * left;
Node * right;
//Set initial value of Binary Tree Node
Node(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
//Define the custom stack class
class MyStack
{
public: Node * element;
MyStack * next;
MyStack(Node * element)
{
this->element = element;
this->next = NULL;
}
};
class BinaryTree
{
public: MyStack * top;
Node * root;
BinaryTree()
{
this->top = NULL;
this->root = NULL;
}
//add element into top of stack
void push(Node * element)
{
MyStack * new_node = new MyStack(element);
if (new_node != NULL)
{
new_node->next = this->top;
this->top = new_node;
}
}
//Remove top element
void pop()
{
if (this->top == NULL)
{
return;
}
MyStack * temp = this->top;
this->top = temp->next;
temp = NULL;
}
//Function which is display the path from leaf to root
void print_path(MyStack * temp)
{
if (temp != NULL)
{
cout << " " << temp->element->data << " ";
print_path(temp->next);
}
}
//This function are collect path information using stack and when get leaf node then displaying node value
void show_path(Node * root)
{
if (root != NULL)
{
//Add a new element into Stack
this->push(root);
this->show_path(root->left);
this->show_path(root->right);
if (root->left == NULL && root->right == NULL)
{
cout << "\n[";
this->print_path(this->top);
cout << " ]\n";
}
this->pop();
}
}
};
int main()
{
BinaryTree obj =  BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
/ \       /
-1   7     8
/ \
9   10
*/
//Insert node into Binary tree
obj.root = new Node(1);
obj.root->left = new Node(2);
obj.root->right = new Node(3);
obj.root->right->right = new Node(6);
obj.root->right->left = new Node(5);
obj.root->left->left = new Node(4);
obj.root->left->left->left = new Node(-1);
obj.root->left->left->right = new Node(7);
obj.root->right->right->left = new Node(8);
obj.root->right->right->left->left = new Node(9);
obj.root->right->right->left->right = new Node(10);
//Display all path between leaf to root
obj.show_path(obj.root);
return 0;
}``````

#### Output

``````[ -1  4  2  1  ]

[ 7  4  2  1  ]

[ 5  3  1  ]

[ 9  8  6  3  1  ]

[ 10  8  6  3  1  ]``````
``````/*
C# Program
Print all paths from leaf node to root
*/
//Tree node
using System;
class Node
{
public int data;
public Node left;
public Node right;
//Set initial value of Binary Tree Node
public Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
//Define the custom stack class
class MyStack
{
public Node element;
public MyStack next;
public MyStack(Node element)
{
this.element = element;
this.next = null;
}
}
class BinaryTree
{
public MyStack top;
public Node root;
public BinaryTree()
{
this.top = null;
this.root = null;
}
//add element into top of stack
public void push(Node element)
{
MyStack new_node = new MyStack(element);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
}
//Remove top element
public void pop()
{
if (this.top == null)
{
return;
}
MyStack temp = this.top;
this.top = temp.next;
temp = null;
}
//Function which is display the path from leaf to root
public void print_path(MyStack temp)
{
if (temp != null)
{
Console.Write(" " + temp.element.data + " ");
print_path(temp.next);
}
}
//This function are collect path information using stack and when get leaf node then displaying node value
public void show_path(Node root)
{
if (root != null)
{
//Add a new element into Stack
this.push(root);
this.show_path(root.left);
this.show_path(root.right);
if (root.left == null && root.right == null)
{
Console.Write("\n[");
this.print_path(this.top);
Console.Write(" ]\n");
}
this.pop();
}
}
public static void Main(String[] args)
{
BinaryTree obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
/ \       /
-1   7     8
/ \
9   10
*/
//Insert node into Binary tree
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.left = new Node(-1);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);
obj.root.right.right.left.left = new Node(9);
obj.root.right.right.left.right = new Node(10);
//Display all path between leaf to root
obj.show_path(obj.root);
}
}``````

#### Output

``````[ -1  4  2  1  ]

[ 7  4  2  1  ]

[ 5  3  1  ]

[ 9  8  6  3  1  ]

[ 10  8  6  3  1  ]``````
``````<?php
/*
Php Program
Print all paths from leaf node to root
*/
//Tree node
class Node
{
public \$data;
public \$left;
public \$right;
//Set initial value of Binary Tree Node
function __construct(\$data)
{
\$this->data = \$data;
\$this->left = null;
\$this->right = null;
}
}
//Define the custom stack class
class MyStack
{
public \$element;
public \$next;

function __construct(\$element)
{
\$this->element = \$element;
\$this->next = null;
}
}
class BinaryTree
{
public \$top;
public \$root;

function __construct()
{
\$this->top = null;
\$this->root = null;
}
//add element into top of stack
function push(\$element)
{
\$new_node = new MyStack(\$element);
if (\$new_node != null)
{
\$new_node->next = \$this->top;
\$this->top = \$new_node;
}
}
//Remove top element
function pop()
{
if (\$this->top == null)
{
return;
}
\$temp = \$this->top;
\$this->top = \$temp->next;
\$temp = null;
}
//Function which is display the path from leaf to root
function print_path(\$temp)
{
if (\$temp != null)
{
echo " ". \$temp->element->data ." ";
\$this->print_path(\$temp->next);
}
}
//This function are collect path information using stack and when get leaf node then displaying node value
function show_path(\$root)
{
if (\$root != null)
{
//Add a new element into Stack
\$this->push(\$root);
\$this->show_path(\$root->left);
\$this->show_path(\$root->right);
if (\$root->left == null && \$root->right == null)
{
echo "\n[";
\$this->print_path(\$this->top);
echo " ]\n";
}
\$this->pop();
}
}
}

function main()
{
\$obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
/ \       /
-1   7     8
/ \
9   10
*/
//Insert node into Binary tree
//Insert node into Binary tree
\$obj->root = new Node(1);
\$obj->root->left = new Node(2);
\$obj->root->right = new Node(3);
\$obj->root->right->right = new Node(6);
\$obj->root->right->left = new Node(5);
\$obj->root->left->left = new Node(4);
\$obj->root->left->left->left = new Node(-1);
\$obj->root->left->left->right = new Node(7);
\$obj->root->right->right->left = new Node(8);
\$obj->root->right->right->left->left = new Node(9);
\$obj->root->right->right->left->right = new Node(10);
//Display all path between leaf to root
\$obj->show_path(\$obj->root);
}
main();``````

#### Output

``````[ -1  4  2  1  ]

[ 7  4  2  1  ]

[ 5  3  1  ]

[ 9  8  6  3  1  ]

[ 10  8  6  3  1  ]``````
``````/*
Node Js Program
Print all paths from leaf node to root
*/
//Tree node
class Node
{
//Set initial value of Binary Tree Node
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
//Define the custom stack class
class MyStack
{
constructor(element)
{
this.element = element;
this.next = null;
}
}
class BinaryTree
{
constructor()
{
this.top = null;
this.root = null;
}
//add element into top of stack
push(element)
{
var new_node = new MyStack(element);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
}
//Remove top element
pop()
{
if (this.top == null)
{
return;
}
var temp = this.top;
this.top = temp.next;
temp = null;
}
//Function which is display the path from leaf to root
print_path(temp)
{
if (temp != null)
{
process.stdout.write(" " + temp.element.data + " ");
this.print_path(temp.next);
}
}
//This function are collect path information using stack and when get leaf node then displaying node value
show_path(root)
{
if (root != null)
{
//Add a new element into Stack
this.push(root);
this.show_path(root.left);
this.show_path(root.right);
if (root.left == null && root.right == null)
{
process.stdout.write("\n[");
this.print_path(this.top);
process.stdout.write(" ]\n");
}
this.pop();
}
}
}

function main()
{
var obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
/ \       /
-1   7     8
/ \
9   10
*/
//Insert node into Binary tree
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.left = new Node(-1);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);
obj.root.right.right.left.left = new Node(9);
obj.root.right.right.left.right = new Node(10);
//Display all path between leaf to root
obj.show_path(obj.root);
}
main();``````

#### Output

``````[ -1  4  2  1  ]

[ 7  4  2  1  ]

[ 5  3  1  ]

[ 9  8  6  3  1  ]

[ 10  8  6  3  1  ]``````
``````#   Python 3 Program
#   Print all paths from leaf node to root

# Tree node
class Node :

# Set initial value of Binary Tree Node
def __init__(self, data) :
self.data = data
self.left = None
self.right = None

# Define the custom stack class
class MyStack :

def __init__(self, element) :
self.element = element
self.next = None

class BinaryTree :

def __init__(self) :
self.top = None
self.root = None

# add element into top of stack
def push(self, element) :
new_node = MyStack(element)
if (new_node != None) :
new_node.next = self.top
self.top = new_node

# Remove top element
def pop(self) :
if (self.top == None) :
return

temp = self.top
self.top = temp.next
temp = None

# Function which is display the path from leaf to root
def print_path(self, temp) :
if (temp != None) :
print(" ", temp.element.data ," ", end = "")
self.print_path(temp.next)

# This function are collect path information using stack and when get leaf node then displaying node value
def show_path(self, root) :
if (root != None) :
# Add a new element into Stack
self.push(root)
self.show_path(root.left)
self.show_path(root.right)
if (root.left == None and root.right == None) :
print("\n[", end = "")
self.print_path(self.top)
print(" ]\n", end = "")

self.pop()

def main() :
obj = BinaryTree()
#  Make A Binary Tree
# 		-----------------------
# 		        1
# 		       /  \
# 		      2    3
# 		     /    /  \
# 		    4    5    6
# 		   / \       /
# 		 -1   7     8
# 		           / \
# 		          9   10
#

# Insert node into Binary tree
obj.root = Node(1)
obj.root.left = Node(2)
obj.root.right = Node(3)
obj.root.right.right = Node(6)
obj.root.right.left = Node(5)
obj.root.left.left = Node(4)
obj.root.left.left.left = Node(-1)
obj.root.left.left.right = Node(7)
obj.root.right.right.left = Node(8)
obj.root.right.right.left.left = Node(9)
obj.root.right.right.left.right = Node(10)
# Display all path between leaf to root
obj.show_path(obj.root)

if __name__ == "__main__": main()``````

#### Output

``````[  -1    4    2    1   ]

[  7    4    2    1   ]

[  5    3    1   ]

[  9    8    6    3    1   ]

[  10    8    6    3    1   ]``````
``````#   Ruby Program
#   Print all paths from leaf node to root

# Tree node
class Node

# Define the accessor and reader of class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right

# Set initial value of Binary Tree Node
def initialize(data)

self.data = data
self.left = nil
self.right = nil
end
end
# Define the custom stack class
class MyStack

# Define the accessor and reader of class MyStack
attr_accessor :element, :next

def initialize(element)

self.element = element
self.next = nil
end
end
class BinaryTree

# Define the accessor and reader of class BinaryTree
attr_accessor :top, :root

def initialize()

self.top = nil
self.root = nil
end
# add element into top of stack
def push(element)

new_node = MyStack.new(element)
if (new_node != nil)

new_node.next = self.top
self.top = new_node
end
end
# Remove top element
def pop()

if (self.top == nil)

return
end
temp = self.top
self.top = temp.next
temp = nil
end
# Function which is display the path from leaf to root
def print_path(temp)

if (temp != nil)

print(" ", temp.element.data ," ")
self.print_path(temp.next)
end
end
# This function are collect path information using stack and when get leaf node then displaying node value
def show_path(root)

if (root != nil)

# Add a new element into Stack
self.push(root)
self.show_path(root.left)
self.show_path(root.right)
if (root.left == nil && root.right == nil)

print("\n[")
self.print_path(self.top)
print(" ]\n")
end
self.pop()
end
end
end
def main()

obj = BinaryTree.new()
#  Make A Binary Tree
# 		-----------------------
# 		        1
# 		       /  \
# 		      2    3
# 		     /    /  \
# 		    4    5    6
# 		   / \       /
# 		 -1   7     8
# 		           / \
# 		          9   10
#

# Insert node into Binary tree
obj.root = Node.new(1)
obj.root.left = Node.new(2)
obj.root.right = Node.new(3)
obj.root.right.right = Node.new(6)
obj.root.right.left = Node.new(5)
obj.root.left.left = Node.new(4)
obj.root.left.left.left = Node.new(-1)
obj.root.left.left.right = Node.new(7)
obj.root.right.right.left = Node.new(8)
obj.root.right.right.left.left = Node.new(9)
obj.root.right.right.left.right = Node.new(10)
# Display all path between leaf to root
obj.show_path(obj.root)
end
main()``````

#### Output

``````[ -1  4  2  1  ]

[ 7  4  2  1  ]

[ 5  3  1  ]

[ 9  8  6  3  1  ]

[ 10  8  6  3  1  ]
``````
``````/*
Scala Program
Print all paths from leaf node to root
*/
//Tree node
class Node(var data: Int,
var left: Node,
var right: Node)
{
//Set initial value of Binary Tree Node
def this(data: Int)
{
this(data,null,null);
}
}
//Define the custom stack class
class MyStack(var element: Node,
var next: MyStack)
{
def this(element: Node)
{
this(element, null);
}
}
class BinaryTree(var top: MyStack,
var root: Node)
{
def this()
{
this(null,null);
}
//add element into top of stack
def push(element: Node): Unit = {
var new_node: MyStack = new MyStack(element);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
}
//Remove top element
def pop(): Unit = {
if (this.top == null)
{
return;
}
var temp: MyStack = this.top;
this.top = temp.next;
temp = null;
}
//Function which is display the path from leaf to root
def print_path(temp: MyStack): Unit = {
if (temp != null)
{
print(" " + temp.element.data + " ");
print_path(temp.next);
}
}
//This function are collect path information using stack and when get leaf node then displaying node value
def show_path(root: Node): Unit = {
if (root != null)
{
//Add a new element into Stack
this.push(root);
this.show_path(root.left);
this.show_path(root.right);
if (root.left == null && root.right == null)
{
print("\n[");
this.print_path(this.top);
print(" ]\n");
}
this.pop();
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: BinaryTree = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
/ \       /
-1   7     8
/ \
9   10
*/
//Insert node into Binary tree
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.left = new Node(-1);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);
obj.root.right.right.left.left = new Node(9);
obj.root.right.right.left.right = new Node(10);
//Display all path between leaf to root
obj.show_path(obj.root);
}
}``````

#### Output

``````[ -1  4  2  1  ]

[ 7  4  2  1  ]

[ 5  3  1  ]

[ 9  8  6  3  1  ]

[ 10  8  6  3  1  ]``````
``````/*
Swift Program
Print all paths from leaf node to root
*/
//Tree node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
//Set initial value of Binary Tree Node
init(_ data: Int)
{
self.data = data;
self.left = nil;
self.right = nil;
}
}
//Define the custom stack class
class MyStack
{
var element: Node? ;
var next: MyStack? ;
init(_ element: Node? )
{
self.element = element;
self.next = nil;
}
}
class BinaryTree
{
var top: MyStack? ;
var root: Node? ;
init()
{
self.top = nil;
self.root = nil;
}
//add element into top of stack
func push(_ element: Node? )
{
let new_node: MyStack? = MyStack(element);
if (new_node != nil)
{
new_node!.next = self.top;
self.top = new_node;
}
}
//Remove top element
func pop()
{
if (self.top == nil)
{
return;
}
var temp: MyStack? = self.top;
self.top = temp!.next;
temp = nil;
}
//Function which is display the path from leaf to root
func print_path(_ temp: MyStack? )
{
if (temp != nil)
{
print(" ", temp!.element!.data ," ", terminator: "");
self.print_path(temp!.next);
}
}
//This function are collect path information using stack and when get leaf node then displaying node value
func show_path(_ root: Node? )
{
if (root != nil)
{
//Add a new element into Stack
self.push(root);
self.show_path(root!.left);
self.show_path(root!.right);
if (root!.left == nil && root!.right == nil)
{
print("\n[", terminator: "");
self.print_path(self.top);
print(" ]\n", terminator: "");
}
self.pop();
}
}
}
func main()
{
let obj: BinaryTree = BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
/ \       /
-1   7     8
/ \
9   10
*/
//Insert node into Binary tree
obj.root = Node(1);
obj.root!.left = Node(2);
obj.root!.right = Node(3);
obj.root!.right!.right = Node(6);
obj.root!.right!.left = Node(5);
obj.root!.left!.left = Node(4);
obj.root!.left!.left!.left = Node(-1);
obj.root!.left!.left!.right = Node(7);
obj.root!.right!.right!.left = Node(8);
obj.root!.right!.right!.left!.left = Node(9);
obj.root!.right!.right!.left!.right = Node(10);
//Display all path between leaf to root
obj.show_path(obj.root);
}
main();``````

#### Output

``````[  -1    4    2    1   ]

[  7    4    2    1   ]

[  5    3    1   ]

[  9    8    6    3    1   ]

[  10    8    6    3    1   ]``````

## Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because we need to visit each node once to collect the paths and print them. The push and pop operations in the stack take constant time, so they do not affect the overall time complexity. Therefore, the time complexity is linear with respect to the number of nodes in the tree.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post