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