Print path from root to a given node in a binary tree

Here given code implementation process.

import java.util.ArrayList;
/*
    Java Program
    Print path from root to a given node in a binary tree
*/
// Binary Tree node
class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public int count;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
		this.count = 0;
	}
	// Display given path 
	public void printPath(ArrayList < Integer > path)
	{
		int i = 0;
		// print path
		while (i < path.size())
		{
			// print path node
			System.out.print(" " + path.get(i));
			i++;
		}
		System.out.print("\n");
	}
	// Find all root to given node path using recursion
	public void findRootToNodePath(TreeNode point, 
                                    ArrayList < Integer > path, int node)
	{
		if (point == null)
		{
			return;
		}
		// Add path element
		path.add(point.data);
		if (point.data == node)
		{
			this.count++;
			printPath(path);
		}
		// Visit left and right subtree using recursion
		findRootToNodePath(point.left, path, node);
		findRootToNodePath(point.right, path, node);
		// Remove last node in path
		path.remove(path.size() - 1);
	}
	// Handles the request of finding root to given node path in tree
	public void rootToNodePath(int node)
	{
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect path
			ArrayList < Integer > path = new ArrayList < Integer > ();
			this.count = 0;
			System.out.println(" \n Given node : " + node);
			findRootToNodePath(this.root, path, node);
			if (this.count == 0)
			{
				System.out.print("None");
			}
		}
	}
	public static void main(String[] args)
	{
		// Create new binary tree
		BinaryTree tree = new BinaryTree();
		/*
		     4                            
		   /   \    
		  9     7    
		 / \     \               
		2   1     12
		   / \    / \
		  6   8  5   18
		 /   /    \
		19  1      15 
		     \      \
		      10     1
		-----------------
		Constructing binary tree    
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(9);
		tree.root.left.right = new TreeNode(1);
		tree.root.left.right.left = new TreeNode(6);
		tree.root.left.right.left.left = new TreeNode(19);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.right.right.left = new TreeNode(1);
		tree.root.left.right.right.left.right = new TreeNode(10);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(7);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.right = new TreeNode(18);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(15);
		tree.root.right.right.left.right.right = new TreeNode(1);
		// Case A
		// All path from root to 1 node
		tree.rootToNodePath(1);
		// Case B
		tree.rootToNodePath(5);
	}
}

input

 Given node : 1
 4 9 1
 4 9 1 8 1
 4 7 12 5 15 1

 Given node : 5
 4 7 12 5
// Include header file
#include <iostream>
#include <vector>
using namespace std;

/*
    C++ Program
    Print path from root to a given node in a binary tree
*/

// Binary Tree node
class TreeNode
{
	public: 
    int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		// Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinaryTree
{
	public: 
    TreeNode *root;
	int count;
	BinaryTree()
	{
		this->root = NULL;
		this->count = 0;
	}
	// Display given path
	void printPath(vector < int > path)
	{
		int i = 0;
		// print path
		while (i < path.size())
		{
			// print path node
			cout << " " << path.at(i);
			i++;
		}
		cout << "\n";
	}
	// Find all root to given node path using recursion
	void findRootToNodePath(TreeNode *point, 
                            vector < int > &path, int node)
	{
		if (point == NULL)
		{
			return;
		}
		// Add path element
		path.push_back(point->data);
		if (point->data == node)
		{
			this->count++;
			this->printPath(path);
		}
		// Visit left and right subtree using recursion
		this->findRootToNodePath(point->left, path, node);
		this->findRootToNodePath(point->right, path, node);
		// Remove last node in path
		path.pop_back();
	}
	// Handles the request of finding root to given node path in tree
	void rootToNodePath(int node)
	{
		if (this->root == NULL)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect path
			vector < int > path;
			this->count = 0;
			cout << " \n Given node : " << node << endl;
			this->findRootToNodePath(this->root, path, node);
			if (this->count == 0)
			{
				cout << "None";
			}
		}
	}
};
int main()
{
	// Create new binary tree
	BinaryTree *tree = new BinaryTree();
	/*
	     4                            
	   /   \    
	  9     7    
	 / \     \               
	2   1     12
	   / \    / \
	  6   8  5   18
	 /   /    \
	19  1      15 
	     \      \
	      10     1
	-----------------
	Constructing binary tree    
	*/
	tree->root = new TreeNode(4);
	tree->root->left = new TreeNode(9);
	tree->root->left->right = new TreeNode(1);
	tree->root->left->right->left = new TreeNode(6);
	tree->root->left->right->left->left = new TreeNode(19);
	tree->root->left->right->right = new TreeNode(8);
	tree->root->left->right->right->left = new TreeNode(1);
	tree->root->left->right->right->left->right = new TreeNode(10);
	tree->root->left->left = new TreeNode(2);
	tree->root->right = new TreeNode(7);
	tree->root->right->right = new TreeNode(12);
	tree->root->right->right->right = new TreeNode(18);
	tree->root->right->right->left = new TreeNode(5);
	tree->root->right->right->left->right = new TreeNode(15);
	tree->root->right->right->left->right->right = new TreeNode(1);
	// Case A
	// All path from root to 1 node
	tree->rootToNodePath(1);
	// Case B
	tree->rootToNodePath(5);
	return 0;
}

input

 Given node : 1
 4 9 1
 4 9 1 8 1
 4 7 12 5 15 1

 Given node : 5
 4 7 12 5
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp Program
    Print path from root to a given node in a binary tree
*/
// Binary Tree node
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public int count;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
		this.count = 0;
	}
	// Display given path
	public void printPath(List < int > path)
	{
		int i = 0;
		// print path
		while (i < path.Count)
		{
			// print path node
			Console.Write(" " + path[i]);
			i++;
		}
		Console.Write("\n");
	}
	// Find all root to given node path using recursion
	public void findRootToNodePath(TreeNode point, 
                                    List < int > path, int node)
	{
		if (point == null)
		{
			return;
		}
		// Add path element
		path.Add(point.data);
		if (point.data == node)
		{
			this.count++;
			this.printPath(path);
		}
		// Visit left and right subtree using recursion
		this.findRootToNodePath(point.left, path, node);
		this.findRootToNodePath(point.right, path, node);
		// Remove last node in path
		path.RemoveAt(path.Count - 1);
	}
	// Handles the request of finding root to given node path in tree
	public void rootToNodePath(int node)
	{
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect path
			List < int > path = new List < int > ();
			this.count = 0;
			Console.WriteLine(" \n Given node : " + node);
			this.findRootToNodePath(this.root, path, node);
			if (this.count == 0)
			{
				Console.Write("None");
			}
		}
	}
	public static void Main(String[] args)
	{
		// Create new binary tree
		BinaryTree tree = new BinaryTree();
		/*
		     4                            
		   /   \    
		  9     7    
		 / \     \               
		2   1     12
		   / \    / \
		  6   8  5   18
		 /   /    \
		19  1      15 
		     \      \
		      10     1
		-----------------
		Constructing binary tree    
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(9);
		tree.root.left.right = new TreeNode(1);
		tree.root.left.right.left = new TreeNode(6);
		tree.root.left.right.left.left = new TreeNode(19);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.right.right.left = new TreeNode(1);
		tree.root.left.right.right.left.right = new TreeNode(10);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(7);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.right = new TreeNode(18);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(15);
		tree.root.right.right.left.right.right = new TreeNode(1);
		// Case A
		// All path from root to 1 node
		tree.rootToNodePath(1);
		// Case B
		tree.rootToNodePath(5);
	}
}

input

 Given node : 1
 4 9 1
 4 9 1 8 1
 4 7 12 5 15 1

 Given node : 5
 4 7 12 5
<?php
/*
    Php Program
    Print path from root to a given node in a binary tree
*/
// Binary Tree node
class TreeNode
{
	public $data;
	public $left;
	public $right;
	public	function __construct($data)
	{
		// Set node value
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class BinaryTree
{
	public $root;
	public $count;
	public	function __construct()
	{
		$this->root = NULL;
		$this->count = 0;
	}
	// Display given path
	public	function printPath($path)
	{
		$i = 0;
		// print path
		while ($i < count($path))
		{
			// print path node
			echo(" ".$path[$i]);
			$i++;
		}
		echo("\n");
	}
	// Find all root to given node path using recursion
	public	function findRootToNodePath($point, &$path, $node)
	{
		if ($point == NULL)
		{
			return;
		}
		// Add path element
		$path[] = $point->data;
		if ($point->data == $node)
		{
			$this->count++;
			$this->printPath($path);
		}
		// Visit left and right subtree using recursion
		$this->findRootToNodePath($point->left, $path, $node);
		$this->findRootToNodePath($point->right, $path, $node);
		// Remove last node in path
		array_pop($path);
	}
	// Handles the request of finding root to given node path in tree
	public	function rootToNodePath($node)
	{
		if ($this->root == NULL)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect path
			$path = array();
			$this->count = 0;
			echo(" \n Given node : ".$node.
				"\n");
			$this->findRootToNodePath($this->root, $path, $node);
			if ($this->count == 0)
			{
				echo("None");
			}
		}
	}
}

function main()
{
	// Create new binary tree
	$tree = new BinaryTree();
	/*
	     4                            
	   /   \    
	  9     7    
	 / \     \               
	2   1     12
	   / \    / \
	  6   8  5   18
	 /   /    \
	19  1      15 
	     \      \
	      10     1
	-----------------
	Constructing binary tree    
	*/
	$tree->root = new TreeNode(4);
	$tree->root->left = new TreeNode(9);
	$tree->root->left->right = new TreeNode(1);
	$tree->root->left->right->left = new TreeNode(6);
	$tree->root->left->right->left->left = new TreeNode(19);
	$tree->root->left->right->right = new TreeNode(8);
	$tree->root->left->right->right->left = new TreeNode(1);
	$tree->root->left->right->right->left->right = new TreeNode(10);
	$tree->root->left->left = new TreeNode(2);
	$tree->root->right = new TreeNode(7);
	$tree->root->right->right = new TreeNode(12);
	$tree->root->right->right->right = new TreeNode(18);
	$tree->root->right->right->left = new TreeNode(5);
	$tree->root->right->right->left->right = new TreeNode(15);
	$tree->root->right->right->left->right->right = new TreeNode(1);
	// Case A
	// All path from root to 1 node
	$tree->rootToNodePath(1);
	// Case B
	$tree->rootToNodePath(5);
}
main();

input

 Given node : 1
 4 9 1
 4 9 1 8 1
 4 7 12 5 15 1

 Given node : 5
 4 7 12 5
/*
    Node JS Program
    Print path from root to a given node in a binary tree
*/
// Binary Tree node
class TreeNode
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
		this.count = 0;
	}
	// Display given path
	printPath(path)
	{
		var i = 0;
		// print path
		while (i < path.length)
		{
			// print path node
			process.stdout.write(" " + path[i]);
			i++;
		}
		process.stdout.write("\n");
	}
	// Find all root to given node path using recursion
	findRootToNodePath(point, path, node)
	{
		if (point == null)
		{
			return;
		}
		// Add path element
		path.push(point.data);
		if (point.data == node)
		{
			this.count++;
			this.printPath(path);
		}
		// Visit left and right subtree using recursion
		this.findRootToNodePath(point.left, path, node);
		this.findRootToNodePath(point.right, path, node);
		// Remove last node in path
		path.pop();
	}
	// Handles the request of finding root to given node path in tree
	rootToNodePath(node)
	{
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect path
			var path = [];
			this.count = 0;
			console.log(" \n Given node : " + node);
			this.findRootToNodePath(this.root, path, node);
			if (this.count == 0)
			{
				process.stdout.write("None");
			}
		}
	}
}

function main()
{
	// Create new binary tree
	var tree = new BinaryTree();
	/*
	     4                            
	   /   \    
	  9     7    
	 / \     \               
	2   1     12
	   / \    / \
	  6   8  5   18
	 /   /    \
	19  1      15 
	     \      \
	      10     1
	-----------------
	Constructing binary tree    
	*/
	tree.root = new TreeNode(4);
	tree.root.left = new TreeNode(9);
	tree.root.left.right = new TreeNode(1);
	tree.root.left.right.left = new TreeNode(6);
	tree.root.left.right.left.left = new TreeNode(19);
	tree.root.left.right.right = new TreeNode(8);
	tree.root.left.right.right.left = new TreeNode(1);
	tree.root.left.right.right.left.right = new TreeNode(10);
	tree.root.left.left = new TreeNode(2);
	tree.root.right = new TreeNode(7);
	tree.root.right.right = new TreeNode(12);
	tree.root.right.right.right = new TreeNode(18);
	tree.root.right.right.left = new TreeNode(5);
	tree.root.right.right.left.right = new TreeNode(15);
	tree.root.right.right.left.right.right = new TreeNode(1);
	// Case A
	// All path from root to 1 node
	tree.rootToNodePath(1);
	// Case B
	tree.rootToNodePath(5);
}
main();

input

 Given node : 1
 4 9 1
 4 9 1 8 1
 4 7 12 5 15 1

 Given node : 5
 4 7 12 5
#    Python 3 Program
#    Print path from root to a given node in a binary tree

#  Binary Tree node
class TreeNode :
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

class BinaryTree :
	def __init__(self) :
		self.root = None
		self.count = 0
	
	#  Display given path
	def printPath(self, path) :
		i = 0
		#  print path
		while (i < len(path)) :
			#  print path node
			print(" ", path[i], end = "")
			i += 1
		
		print(end = "\n")
	
	#  Find all root to given node path using recursion
	def findRootToNodePath(self, point, path, node) :
		if (point == None) :
			return
		
		#  Add path element
		path.append(point.data)
		if (point.data == node) :
			self.count += 1
			self.printPath(path)
		
		#  Visit left and right subtree using recursion
		self.findRootToNodePath(point.left, path, node)
		self.findRootToNodePath(point.right, path, node)
		#  Remove last node in path
		del path[len(path) - 1]
	
	#  Handles the request of finding root to given node path in tree
	def rootToNodePath(self, node) :
		if (self.root == None) :
			#  Empty Tree
			return
		else :
			#  This is use to collect path
			path = []
			self.count = 0
			print(" \n Given node : ", node)
			self.findRootToNodePath(self.root, path, node)
			if (self.count == 0) :
				print("None", end = "")
			
		
	

def main() :
	#  Create new binary tree
	tree = BinaryTree()
	#     4                            
	#    /   \    
	#   9     7    
	#  / \     \               
	# 2   1     12
	#    / \    / \
	#   6   8  5   18
	#  /   /    \
	# 19  1      15 
	#      \      \
	#       10     1
	# -----------------
	# Constructing binary tree    
	tree.root = TreeNode(4)
	tree.root.left = TreeNode(9)
	tree.root.left.right = TreeNode(1)
	tree.root.left.right.left = TreeNode(6)
	tree.root.left.right.left.left = TreeNode(19)
	tree.root.left.right.right = TreeNode(8)
	tree.root.left.right.right.left = TreeNode(1)
	tree.root.left.right.right.left.right = TreeNode(10)
	tree.root.left.left = TreeNode(2)
	tree.root.right = TreeNode(7)
	tree.root.right.right = TreeNode(12)
	tree.root.right.right.right = TreeNode(18)
	tree.root.right.right.left = TreeNode(5)
	tree.root.right.right.left.right = TreeNode(15)
	tree.root.right.right.left.right.right = TreeNode(1)
	#  Case A
	#  All path from root to 1 node
	tree.rootToNodePath(1)
	#  Case B
	tree.rootToNodePath(5)

if __name__ == "__main__": main()

input

 Given node :  1
  4  9  1
  4  9  1  8  1
  4  7  12  5  15  1

 Given node :  5
  4  7  12  5
#    Ruby Program
#    Print path from root to a given node in a binary tree

#  Binary Tree node
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(data) 
		#  Set node value
		self.data = data
		self.left = nil
		self.right = nil
	end

end

class BinaryTree 
	# Define the accessor and reader of class BinaryTree
	attr_reader :root, :count
	attr_accessor :root, :count
	def initialize() 
		self.root = nil
		self.count = 0
	end

	#  Display given path
	def printPath(path) 
		i = 0
		#  print path
		while (i < path.length) 
			#  print path node
			print(" ", path[i])
			i += 1
		end

		print("\n")
	end

	#  Find all root to given node path using recursion
	def findRootToNodePath(point, path, node) 
		if (point == nil) 
			return
		end

		#  Add path element
		path.push(point.data)
		if (point.data == node) 
			self.count += 1
			self.printPath(path)
		end

		#  Visit left and right subtree using recursion
		self.findRootToNodePath(point.left, path, node)
		self.findRootToNodePath(point.right, path, node)
		#  Remove last node in path
		path.delete_at(path.length - 1)
	end

	#  Handles the request of finding root to given node path in tree
	def rootToNodePath(node) 
		if (self.root == nil) 
			#  Empty Tree
			return
		else
 
			#  This is use to collect path
			path = []
			self.count = 0
			print(" \n Given node : ", node, "\n")
			self.findRootToNodePath(self.root, path, node)
			if (self.count == 0) 
				print("None")
			end

		end

	end

end

def main() 
	#  Create new binary tree
	tree = BinaryTree.new()
	#     4                            
	#    /   \    
	#   9     7    
	#  / \     \               
	# 2   1     12
	#    / \    / \
	#   6   8  5   18
	#  /   /    \
	# 19  1      15 
	#      \      \
	#       10     1
	# -----------------
	# Constructing binary tree    
	tree.root = TreeNode.new(4)
	tree.root.left = TreeNode.new(9)
	tree.root.left.right = TreeNode.new(1)
	tree.root.left.right.left = TreeNode.new(6)
	tree.root.left.right.left.left = TreeNode.new(19)
	tree.root.left.right.right = TreeNode.new(8)
	tree.root.left.right.right.left = TreeNode.new(1)
	tree.root.left.right.right.left.right = TreeNode.new(10)
	tree.root.left.left = TreeNode.new(2)
	tree.root.right = TreeNode.new(7)
	tree.root.right.right = TreeNode.new(12)
	tree.root.right.right.right = TreeNode.new(18)
	tree.root.right.right.left = TreeNode.new(5)
	tree.root.right.right.left.right = TreeNode.new(15)
	tree.root.right.right.left.right.right = TreeNode.new(1)
	#  Case A
	#  All path from root to 1 node
	tree.rootToNodePath(1)
	#  Case B
	tree.rootToNodePath(5)
end

main()

input

 
 Given node : 1
 4 9 1
 4 9 1 8 1
 4 7 12 5 15 1
 
 Given node : 5
 4 7 12 5
import scala.collection.mutable._;
/*
    Scala Program
    Print path from root to a given node in a binary tree
*/
// Binary Tree node
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		// Set node value
		this(data,null,null);
	}
}
class BinaryTree(var root: TreeNode,
	var count: Int)
{
	def this()
	{
		this(null,0);
	}
	// Display given path
	def printPath(path: ArrayBuffer[Int]): Unit = {
		var i: Int = 0;
		// print path
		while (i < path.size)
		{
			// print path node
			print(" " + path(i));
			i += 1;
		}
		print("\n");
	}
	// Find all root to given node path using recursion
	def findRootToNodePath(point: TreeNode, path: ArrayBuffer[Int], node: Int): Unit = {
		if (point == null)
		{
			return;
		}
		// Add path element
		path += point.data;
		if (point.data == node)
		{
			this.count += 1;
			printPath(path);
		}
		// Visit left and right subtree using recursion
		findRootToNodePath(point.left, path, node);
		findRootToNodePath(point.right, path, node);
		// Remove last node in path
		path.remove(path.size - 1);
	}
	// Handles the request of finding root to given node path in tree
	def rootToNodePath(node: Int): Unit = {
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect path
			var path: ArrayBuffer[Int] = new ArrayBuffer[Int]();
			this.count = 0;
			println(" \n Given node : " + node);
			findRootToNodePath(this.root, path, node);
			if (this.count == 0)
			{
				print("None");
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create new binary tree
		var tree: BinaryTree = new BinaryTree();
		/*
		     4                            
		   /   \    
		  9     7    
		 / \     \               
		2   1     12
		   / \    / \
		  6   8  5   18
		 /   /    \
		19  1      15 
		     \      \
		      10     1
		-----------------
		Constructing binary tree    
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(9);
		tree.root.left.right = new TreeNode(1);
		tree.root.left.right.left = new TreeNode(6);
		tree.root.left.right.left.left = new TreeNode(19);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.right.right.left = new TreeNode(1);
		tree.root.left.right.right.left.right = new TreeNode(10);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(7);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.right = new TreeNode(18);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(15);
		tree.root.right.right.left.right.right = new TreeNode(1);
		// Case A
		// All path from root to 1 node
		tree.rootToNodePath(1);
		// Case B
		tree.rootToNodePath(5);
	}
}

input

 Given node : 1
 4 9 1
 4 9 1 8 1
 4 7 12 5 15 1

 Given node : 5
 4 7 12 5
import Foundation;
/*
    Swift 4 Program
    Print path from root to a given node in a binary tree
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		// Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	var count: Int;
	init()
	{
		self.root = nil;
		self.count = 0;
	}
	// Display given path
	func printPath(_ path: [Int])
	{
		var i = 0;
		// print path
		while (i < path.count)
		{
			// print path node
			print(" ", path[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Find all root to given node path using recursion
	func findRootToNodePath(_ point: TreeNode? , _ path : inout[Int], _ node: Int)
	{
		if (point == nil)
		{
			return;
		}
		// Add path element
		path.append(point!.data);
		if (point!.data == node)
		{
			self.count += 1;
			self.printPath(path);
		}
		// Visit left and right subtree using recursion
		self.findRootToNodePath(point!.left, &path, node);
		self.findRootToNodePath(point!.right, &path, node);
		// Remove last node in path
		path.removeLast();
	}
	// Handles the request of finding root to given node path in tree
	func rootToNodePath(_ node: Int)
	{
		if (self.root == nil)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect path
			var path = [Int]();
			self.count = 0;
			print(" \n Given node : ", node);
			self.findRootToNodePath(self.root, &path, node);
			if (self.count == 0)
			{
				print("None", terminator: "");
			}
		}
	}
}
func main()
{
	// Create new binary tree
	let tree = BinaryTree();
	/*
	     4                            
	   /   \    
	  9     7    
	 / \     \               
	2   1     12
	   / \    / \
	  6   8  5   18
	 /   /    \
	19  1      15 
	     \      \
	      10     1
	-----------------
	Constructing binary tree    
	*/
	tree.root = TreeNode(4);
	tree.root!.left = TreeNode(9);
	tree.root!.left!.right = TreeNode(1);
	tree.root!.left!.right!.left = TreeNode(6);
	tree.root!.left!.right!.left!.left = TreeNode(19);
	tree.root!.left!.right!.right = TreeNode(8);
	tree.root!.left!.right!.right!.left = TreeNode(1);
	tree.root!.left!.right!.right!.left!.right = TreeNode(10);
	tree.root!.left!.left = TreeNode(2);
	tree.root!.right = TreeNode(7);
	tree.root!.right!.right = TreeNode(12);
	tree.root!.right!.right!.right = TreeNode(18);
	tree.root!.right!.right!.left = TreeNode(5);
	tree.root!.right!.right!.left!.right = TreeNode(15);
	tree.root!.right!.right!.left!.right!.right = TreeNode(1);
	// Case A
	// All path from root to 1 node
	tree.rootToNodePath(1);
	// Case B
	tree.rootToNodePath(5);
}
main();

input

 Given node :  1
  4  9  1
  4  9  1  8  1
  4  7  12  5  15  1

 Given node :  5
  4  7  12  5
/*
    Kotlin Program
    Print path from root to a given node in a binary tree
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	var root: TreeNode ? ;
	var count: Int;
	constructor()
	{
		this.root = null;
		this.count = 0;
	}
	// Display given path
	fun printPath(path: MutableList < Int > ): Unit
	{
		var i: Int = 0;
		// print path
		while (i < path.size)
		{
			// print path node
			print(" " + path[i]);
			i += 1;
		}
		print("\n");
	}
	// Find all root to given node path using recursion
	fun findRootToNodePath(point: TreeNode ? , 
                           path : MutableList < Int >  , node : Int): Unit
	{
		if (point == null)
		{
			return;
		}
		// Add path element
		path.add(point.data);
		if (point.data == node)
		{
			this.count += 1;
			this.printPath(path);
		}
		// Visit left and right subtree using recursion
		this.findRootToNodePath(point.left, path, node);
		this.findRootToNodePath(point.right, path, node);
		// Remove last node in path
		path.removeAt(path.size - 1);
	}
	// Handles the request of finding root to given node path in tree
	fun rootToNodePath(node: Int): Unit
	{
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// This is use to collect path
			var path: MutableList < Int > = mutableListOf < Int > ();
			this.count = 0;
			println(" \n Given node : " + node);
			this.findRootToNodePath(this.root, path, node);
			if (this.count == 0)
			{
				print("None");
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Create new binary tree
	val tree: BinaryTree = BinaryTree();
	/*
	     4                            
	   /   \    
	  9     7    
	 / \     \               
	2   1     12
	   / \    / \
	  6   8  5   18
	 /   /    \
	19  1      15 
	     \      \
	      10     1
	-----------------
	Constructing binary tree    
	*/
	tree.root = TreeNode(4);
	tree.root?.left = TreeNode(9);
	tree.root?.left?.right = TreeNode(1);
	tree.root?.left?.right?.left = TreeNode(6);
	tree.root?.left?.right?.left?.left = TreeNode(19);
	tree.root?.left?.right?.right = TreeNode(8);
	tree.root?.left?.right?.right?.left = TreeNode(1);
	tree.root?.left?.right?.right?.left?.right = TreeNode(10);
	tree.root?.left?.left = TreeNode(2);
	tree.root?.right = TreeNode(7);
	tree.root?.right?.right = TreeNode(12);
	tree.root?.right?.right?.right = TreeNode(18);
	tree.root?.right?.right?.left = TreeNode(5);
	tree.root?.right?.right?.left?.right = TreeNode(15);
	tree.root?.right?.right?.left?.right?.right = TreeNode(1);
	// Case A
	// All path from root to 1 node
	tree.rootToNodePath(1);
	// Case B
	tree.rootToNodePath(5);
}

input

 Given node : 1
 4 9 1
 4 9 1 8 1
 4 7 12 5 15 1

 Given node : 5
 4 7 12 5


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.

New Comment







© 2021, kalkicode.com, All rights reserved