Print all nodes at distance k from a given node

Here given code implementation process.
/*
Java Program
Print all nodes at distance k from a given node
*/
// 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 boolean result;
public int count;
public BinaryTree()
{
// Set initial value
this.root = null;
this.result = false;
this.count = 0;
}
public void printBottomK(TreeNode track, int k)
{
if (track != null)
{
if (k == 0)
{
System.out.print(" " + track.data);
this.result = true;
return;
}
printBottomK(track.left, k - 1);
printBottomK(track.right, k - 1);
}
}
public TreeNode findResult(TreeNode track, TreeNode node, int k)
{
if (track != null && this.count <= k)
{
if (track == node)
{
return track;
}
else
{
TreeNode point = findResult(track.left, node, k);
if (point == null)
{
point = findResult(track.right, node, k);
}
if (point != null)
{
this.count += 1;
if (this.count == k)
{
// Current path node
System.out.print(" " + track.data);
this.result = true;
}
else if (track.left == point && this.count < k)
{
printBottomK(track.right, k - (this.count + 1));
}
else if (track.right == point && this.count < k)
{
printBottomK(track.left, k - (this.count + 1));
}
return track;
}
}
}
return null;
}
// This function are handle the request of finding
// every k distance node from given node.
public void distanceKfromNode(TreeNode node, int k)
{
if (k <= 0 || node == null)
{
return;
}
this.result = false;
this.count = 0;
System.out.println("\n Given node " +
(node.data) + " and distance K " + k);
// Print bottom element
printBottomK(node, k);
findResult(this.root, node, k);
if (this.result == false)
{
System.out.print(" No result \n");
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
Binary Tree
------------
10
/ \
-2 5
/ \ / \
1 3 7 2
/ \ \
9 8 4
/
11
\
10
*/
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(-2);
tree.root.right = new TreeNode(5);
tree.root.right.right = new TreeNode(2);
tree.root.right.right.right = new TreeNode(4);
tree.root.right.left = new TreeNode(7);
tree.root.right.left.right = new TreeNode(8);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(9);
tree.root.right.left.right.left = new TreeNode(11);
tree.root.right.left.right.left.right = new TreeNode(10);
// Test A
// K = 3
// 10
// /
// -5 <- node
TreeNode node = tree.root.left;
tree.distanceKfromNode(node, 3);
// Test B
// K = 3
// 10
// \
// 5
// /
// 7 <- node
node = tree.root.right.left;
tree.distanceKfromNode(node, 3);
// Test B
// K = 4
// 10
// \
// 5
// \
// 2 <- node
node = tree.root.right.right;
tree.distanceKfromNode(node, 4);
}
}
Output
Given node -2 and distance K 3
7 2
Given node 7 and distance K 3
10 4 -2
Given node 2 and distance K 4
11 1 3
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Print all nodes at distance k from a given node
*/
// 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;
bool result;
int count;
BinaryTree()
{
this->root = NULL;
this->result = false;
this->count = 0;
}
void printBottomK(TreeNode *track, int k)
{
if (track != NULL)
{
if (k == 0)
{
cout << " " << track->data;
this->result = true;
return;
}
this->printBottomK(track->left, k - 1);
this->printBottomK(track->right, k - 1);
}
}
TreeNode *findResult(TreeNode *track, TreeNode *node, int k)
{
if (track != NULL && this->count <= k)
{
if (track == node)
{
return track;
}
else
{
TreeNode *point = this->findResult(track->left, node, k);
if (point == NULL)
{
point = this->findResult(track->right, node, k);
}
if (point != NULL)
{
this->count += 1;
if (this->count == k)
{
// Current path node
cout << " " << track->data;
this->result = true;
}
else if (track->left == point && this->count < k)
{
this->printBottomK(track->right,
k - (this->count + 1));
}
else if (track->right == point && this->count < k)
{
this->printBottomK(track->left,
k - (this->count + 1));
}
return track;
}
}
}
return NULL;
}
// This function are handle the request of finding
// every k distance node from given node.
void distanceKfromNode(TreeNode *node, int k)
{
if (k <= 0 || node == NULL)
{
return;
}
this->result = false;
this->count = 0;
cout << "\n Given node "
<< (node->data)
<< " and distance K "
<< k << endl;
// Print bottom element
this->printBottomK(node, k);
this->findResult(this->root, node, k);
if (this->result == false)
{
cout << " No result \n";
}
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*
Binary Tree
------------
10
/ \
-2 5
/ \ / \
1 3 7 2
/ \ \
9 8 4
/
11
\
10
*/
tree->root = new TreeNode(10);
tree->root->left = new TreeNode(-2);
tree->root->right = new TreeNode(5);
tree->root->right->right = new TreeNode(2);
tree->root->right->right->right = new TreeNode(4);
tree->root->right->left = new TreeNode(7);
tree->root->right->left->right = new TreeNode(8);
tree->root->left->left = new TreeNode(1);
tree->root->left->right = new TreeNode(3);
tree->root->left->right->left = new TreeNode(9);
tree->root->right->left->right->left = new TreeNode(11);
tree->root->right->left->right->left->right = new TreeNode(10);
// Test A
// K = 3
// 10
// /
// -5 <- node
TreeNode *node = tree->root->left;
tree->distanceKfromNode(node, 3);
// Test B
// K = 3
// 10
// \
// 5
// /
// 7 <- node
node = tree->root->right->left;
tree->distanceKfromNode(node, 3);
// Test B
// K = 4
// 10
// \
// 5
// \
// 2 <- node
node = tree->root->right->right;
tree->distanceKfromNode(node, 4);
return 0;
}
Output
Given node -2 and distance K 3
7 2
Given node 7 and distance K 3
10 4 -2
Given node 2 and distance K 4
11 1 3
// Include namespace system
using System;
/*
Csharp Program
Print all nodes at distance k from a given node
*/
// 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 Boolean result;
public int count;
public BinaryTree()
{
// Set initial value
this.root = null;
this.result = false;
this.count = 0;
}
public void printBottomK(TreeNode track, int k)
{
if (track != null)
{
if (k == 0)
{
Console.Write(" " + track.data);
this.result = true;
return;
}
this.printBottomK(track.left, k - 1);
this.printBottomK(track.right, k - 1);
}
}
public TreeNode findResult(TreeNode track,
TreeNode node, int k)
{
if (track != null && this.count <= k)
{
if (track == node)
{
return track;
}
else
{
TreeNode point = this.findResult(track.left, node, k);
if (point == null)
{
point = this.findResult(track.right, node, k);
}
if (point != null)
{
this.count += 1;
if (this.count == k)
{
// Current path node
Console.Write(" " + track.data);
this.result = true;
}
else if (track.left == point && this.count < k)
{
this.printBottomK(track.right, k - (this.count + 1));
}
else if (track.right == point && this.count < k)
{
this.printBottomK(track.left, k - (this.count + 1));
}
return track;
}
}
}
return null;
}
// This function are handle the request of finding
// every k distance node from given node.
public void distanceKfromNode(TreeNode node, int k)
{
if (k <= 0 || node == null)
{
return;
}
this.result = false;
this.count = 0;
Console.WriteLine("\n Given node " + (node.data) + " and distance K " + k);
// Print bottom element
this.printBottomK(node, k);
this.findResult(this.root, node, k);
if (this.result == false)
{
Console.Write(" No result \n");
}
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
Binary Tree
------------
10
/ \
-2 5
/ \ / \
1 3 7 2
/ \ \
9 8 4
/
11
\
10
*/
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(-2);
tree.root.right = new TreeNode(5);
tree.root.right.right = new TreeNode(2);
tree.root.right.right.right = new TreeNode(4);
tree.root.right.left = new TreeNode(7);
tree.root.right.left.right = new TreeNode(8);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(9);
tree.root.right.left.right.left = new TreeNode(11);
tree.root.right.left.right.left.right = new TreeNode(10);
// Test A
// K = 3
// 10
// /
// -5 <- node
TreeNode node = tree.root.left;
tree.distanceKfromNode(node, 3);
// Test B
// K = 3
// 10
// \
// 5
// /
// 7 <- node
node = tree.root.right.left;
tree.distanceKfromNode(node, 3);
// Test B
// K = 4
// 10
// \
// 5
// \
// 2 <- node
node = tree.root.right.right;
tree.distanceKfromNode(node, 4);
}
}
Output
Given node -2 and distance K 3
7 2
Given node 7 and distance K 3
10 4 -2
Given node 2 and distance K 4
11 1 3
package main
import "fmt"
/*
Go Program
Print all nodes at distance k from a given node
*/
// Binary Tree node
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
// Set node value
me.data = data
me.left = nil
me.right = nil
return me
}
type BinaryTree struct {
root * TreeNode
result bool
count int
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
// Set initial value
me.root = nil
me.result = false
me.count = 0
return me
}
func(this *BinaryTree) printBottomK(track * TreeNode,
k int) {
if track != nil {
if k == 0 {
fmt.Print(" ", track.data)
this.result = true
return
}
this.printBottomK(track.left, k - 1)
this.printBottomK(track.right, k - 1)
}
}
func(this *BinaryTree) findResult(track * TreeNode,
node * TreeNode, k int) * TreeNode {
if track != nil && this.count <= k {
if track == node {
return track
} else {
var point * TreeNode = this.findResult(track.left,
node, k)
if point == nil {
point = this.findResult(track.right, node, k)
}
if point != nil {
this.count += 1
if this.count == k {
// Current path node
fmt.Print(" ", track.data)
this.result = true
} else if track.left == point && this.count < k {
this.printBottomK(track.right,
k - (this.count + 1))
} else if track.right == point && this.count < k {
this.printBottomK(track.left,
k - (this.count + 1))
}
return track
}
}
}
return nil
}
// This function are handle the request of finding
// every k distance node from given node.
func(this BinaryTree) distanceKfromNode(node * TreeNode,
k int) {
if k <= 0 || node == nil {
return
}
this.result = false
this.count = 0
fmt.Println("\n Given node ",
(node.data), " and distance K ", k)
// Print bottom element
this.printBottomK(node, k)
this.findResult(this.root, node, k)
if this.result == false {
fmt.Print(" No result \n")
}
}
func main() {
var tree * BinaryTree = getBinaryTree()
/*
Binary Tree
------------
10
/ \
-2 5
/ \ / \
1 3 7 2
/ \ \
9 8 4
/
11
\
10
*/
tree.root = getTreeNode(10)
tree.root.left = getTreeNode(-2)
tree.root.right = getTreeNode(5)
tree.root.right.right = getTreeNode(2)
tree.root.right.right.right = getTreeNode(4)
tree.root.right.left = getTreeNode(7)
tree.root.right.left.right = getTreeNode(8)
tree.root.left.left = getTreeNode(1)
tree.root.left.right = getTreeNode(3)
tree.root.left.right.left = getTreeNode(9)
tree.root.right.left.right.left = getTreeNode(11)
tree.root.right.left.right.left.right = getTreeNode(10)
// Test A
// K = 3
// 10
// /
// -5 <- node
var node * TreeNode = tree.root.left
tree.distanceKfromNode(node, 3)
// Test B
// K = 3
// 10
// \
// 5
// /
// 7 <- node
node = tree.root.right.left
tree.distanceKfromNode(node, 3)
// Test B
// K = 4
// 10
// \
// 5
// \
// 2 <- node
node = tree.root.right.right
tree.distanceKfromNode(node, 4)
}
Output
Given node -2 and distance K 3
7 2
Given node 7 and distance K 3
10 4 -2
Given node 2 and distance K 4
11 1 3
<?php
/*
Php Program
Print all nodes at distance k from a given node
*/
// 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 $result;
public $count;
public function __construct()
{
$this->root = NULL;
$this->result = false;
$this->count = 0;
}
public function printBottomK($track, $k)
{
if ($track != NULL)
{
if ($k == 0)
{
echo(" ".$track->data);
$this->result = true;
return;
}
$this->printBottomK($track->left, $k - 1);
$this->printBottomK($track->right, $k - 1);
}
}
public function findResult($track, $node, $k)
{
if ($track != NULL && $this->count <= $k)
{
if ($track == $node)
{
return $track;
}
else
{
$point = $this->findResult($track->left, $node, $k);
if ($point == NULL)
{
$point = $this->findResult($track->right, $node, $k);
}
if ($point != NULL)
{
$this->count += 1;
if ($this->count == $k)
{
// Current path node
echo(" ".$track->data);
$this->result = true;
}
else if ($track->left == $point && $this->count < $k)
{
$this->printBottomK($track->right,
$k - ($this->count + 1));
}
else if ($track->right == $point && $this->count < $k)
{
$this->printBottomK($track->left,
$k - ($this->count + 1));
}
return $track;
}
}
}
return NULL;
}
// This function are handle the request of finding
// every k distance node from given node.
public function distanceKfromNode($node, $k)
{
if ($k <= 0 || $node == NULL)
{
return;
}
$this->result = false;
$this->count = 0;
echo("\n Given node ".($node->data).
" and distance K ".$k.
"\n");
// Print bottom element
$this->printBottomK($node, $k);
$this->findResult($this->root, $node, $k);
if ($this->result == false)
{
echo(" No result \n");
}
}
}
function main()
{
$tree = new BinaryTree();
/*
Binary Tree
------------
10
/ \
-2 5
/ \ / \
1 3 7 2
/ \ \
9 8 4
/
11
\
10
*/
$tree->root = new TreeNode(10);
$tree->root->left = new TreeNode(-2);
$tree->root->right = new TreeNode(5);
$tree->root->right->right = new TreeNode(2);
$tree->root->right->right->right = new TreeNode(4);
$tree->root->right->left = new TreeNode(7);
$tree->root->right->left->right = new TreeNode(8);
$tree->root->left->left = new TreeNode(1);
$tree->root->left->right = new TreeNode(3);
$tree->root->left->right->left = new TreeNode(9);
$tree->root->right->left->right->left = new TreeNode(11);
$tree->root->right->left->right->left->right = new TreeNode(10);
// Test A
// K = 3
// 10
// /
// -5 <- node
$node = $tree->root->left;
$tree->distanceKfromNode($node, 3);
// Test B
// K = 3
// 10
// \
// 5
// /
// 7 <- node
$node = $tree->root->right->left;
$tree->distanceKfromNode($node, 3);
// Test B
// K = 4
// 10
// \
// 5
// \
// 2 <- node
$node = $tree->root->right->right;
$tree->distanceKfromNode($node, 4);
}
main();
Output
Given node -2 and distance K 3
7 2
Given node 7 and distance K 3
10 4 -2
Given node 2 and distance K 4
11 1 3
/*
Node JS Program
Print all nodes at distance k from a given node
*/
// 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.result = false;
this.count = 0;
}
printBottomK(track, k)
{
if (track != null)
{
if (k == 0)
{
process.stdout.write(" " + track.data);
this.result = true;
return;
}
this.printBottomK(track.left, k - 1);
this.printBottomK(track.right, k - 1);
}
}
findResult(track, node, k)
{
if (track != null && this.count <= k)
{
if (track == node)
{
return track;
}
else
{
var point = this.findResult(track.left, node, k);
if (point == null)
{
point = this.findResult(track.right, node, k);
}
if (point != null)
{
this.count += 1;
if (this.count == k)
{
// Current path node
process.stdout.write(" " + track.data);
this.result = true;
}
else if (track.left == point && this.count < k)
{
this.printBottomK(track.right,
k - (this.count + 1));
}
else if (track.right == point && this.count < k)
{
this.printBottomK(track.left,
k - (this.count + 1));
}
return track;
}
}
}
return null;
}
// This function are handle the request of finding
// every k distance node from given node.
distanceKfromNode(node, k)
{
if (k <= 0 || node == null)
{
return;
}
this.result = false;
this.count = 0;
console.log("\n Given node " +
(node.data) + " and distance K " + k);
// Print bottom element
this.printBottomK(node, k);
this.findResult(this.root, node, k);
if (this.result == false)
{
process.stdout.write(" No result \n");
}
}
}
function main()
{
var tree = new BinaryTree();
/*
Binary Tree
------------
10
/ \
-2 5
/ \ / \
1 3 7 2
/ \ \
9 8 4
/
11
\
10
*/
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(-2);
tree.root.right = new TreeNode(5);
tree.root.right.right = new TreeNode(2);
tree.root.right.right.right = new TreeNode(4);
tree.root.right.left = new TreeNode(7);
tree.root.right.left.right = new TreeNode(8);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(9);
tree.root.right.left.right.left = new TreeNode(11);
tree.root.right.left.right.left.right = new TreeNode(10);
// Test A
// K = 3
// 10
// /
// -5 <- node
var node = tree.root.left;
tree.distanceKfromNode(node, 3);
// Test B
// K = 3
// 10
// \
// 5
// /
// 7 <- node
node = tree.root.right.left;
tree.distanceKfromNode(node, 3);
// Test B
// K = 4
// 10
// \
// 5
// \
// 2 <- node
node = tree.root.right.right;
tree.distanceKfromNode(node, 4);
}
main();
Output
Given node -2 and distance K 3
7 2
Given node 7 and distance K 3
10 4 -2
Given node 2 and distance K 4
11 1 3
# Python 3 Program
# Print all nodes at distance k from a given node
# 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.result = False
self.count = 0
def printBottomK(self, track, k) :
if (track != None) :
if (k == 0) :
print(" ", track.data, end = "")
self.result = True
return
self.printBottomK(track.left, k - 1)
self.printBottomK(track.right, k - 1)
def findResult(self, track, node, k) :
if (track != None and self.count <= k) :
if (track == node) :
return track
else :
point = self.findResult(track.left, node, k)
if (point == None) :
point = self.findResult(track.right, node, k)
if (point != None) :
self.count += 1
if (self.count == k) :
# Current path node
print(" ", track.data, end = "")
self.result = True
elif (track.left == point and self.count < k) :
self.printBottomK(track.right, k - (self.count + 1))
elif (track.right == point and self.count < k) :
self.printBottomK(track.left, k - (self.count + 1))
return track
return None
# This function are handle the request of finding
# every k distance node from given node.
def distanceKfromNode(self, node, k) :
if (k <= 0 or node == None) :
return
self.result = False
self.count = 0
print("\n Given node ", (node.data) ," and distance K ", k)
# Print bottom element
self.printBottomK(node, k)
self.findResult(self.root, node, k)
if (self.result == False) :
print(" No result ")
def main() :
tree = BinaryTree()
# Binary Tree
# ------------
# 10
# / \
# -2 5
# / \ / \
# 1 3 7 2
# / \ \
# 9 8 4
# /
# 11
# \
# 10
tree.root = TreeNode(10)
tree.root.left = TreeNode(-2)
tree.root.right = TreeNode(5)
tree.root.right.right = TreeNode(2)
tree.root.right.right.right = TreeNode(4)
tree.root.right.left = TreeNode(7)
tree.root.right.left.right = TreeNode(8)
tree.root.left.left = TreeNode(1)
tree.root.left.right = TreeNode(3)
tree.root.left.right.left = TreeNode(9)
tree.root.right.left.right.left = TreeNode(11)
tree.root.right.left.right.left.right = TreeNode(10)
# Test A
# K = 3
# 10
# /
# -5 <- node
node = tree.root.left
tree.distanceKfromNode(node, 3)
# Test B
# K = 3
# 10
# \
# 5
# /
# 7 <- node
node = tree.root.right.left
tree.distanceKfromNode(node, 3)
# Test B
# K = 4
# 10
# \
# 5
# \
# 2 <- node
node = tree.root.right.right
tree.distanceKfromNode(node, 4)
if __name__ == "__main__": main()
Output
Given node -2 and distance K 3
7 2
Given node 7 and distance K 3
10 4 -2
Given node 2 and distance K 4
11 1 3
# Ruby Program
# Print all nodes at distance k from a given node
# 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, :result, :count
attr_accessor :root, :result, :count
def initialize()
self.root = nil
self.result = false
self.count = 0
end
def printBottomK(track, k)
if (track != nil)
if (k == 0)
print(" ", track.data)
self.result = true
return
end
self.printBottomK(track.left, k - 1)
self.printBottomK(track.right, k - 1)
end
end
def findResult(track, node, k)
if (track != nil && self.count <= k)
if (track == node)
return track
else
point = self.findResult(track.left, node, k)
if (point == nil)
point = self.findResult(track.right, node, k)
end
if (point != nil)
self.count += 1
if (self.count == k)
# Current path node
print(" ", track.data)
self.result = true
elsif (track.left == point && self.count < k)
self.printBottomK(track.right,
k - (self.count + 1))
elsif (track.right == point && self.count < k)
self.printBottomK(track.left,
k - (self.count + 1))
end
return track
end
end
end
return nil
end
# This function are handle the request of finding
# every k distance node from given node.
def distanceKfromNode(node, k)
if (k <= 0 || node == nil)
return
end
self.result = false
self.count = 0
print("\n Given node ", (node.data) ," and distance K ", k, "\n")
# Print bottom element
self.printBottomK(node, k)
self.findResult(self.root, node, k)
if (self.result == false)
print(" No result \n")
end
end
end
def main()
tree = BinaryTree.new()
# Binary Tree
# ------------
# 10
# / \
# -2 5
# / \ / \
# 1 3 7 2
# / \ \
# 9 8 4
# /
# 11
# \
# 10
tree.root = TreeNode.new(10)
tree.root.left = TreeNode.new(-2)
tree.root.right = TreeNode.new(5)
tree.root.right.right = TreeNode.new(2)
tree.root.right.right.right = TreeNode.new(4)
tree.root.right.left = TreeNode.new(7)
tree.root.right.left.right = TreeNode.new(8)
tree.root.left.left = TreeNode.new(1)
tree.root.left.right = TreeNode.new(3)
tree.root.left.right.left = TreeNode.new(9)
tree.root.right.left.right.left = TreeNode.new(11)
tree.root.right.left.right.left.right = TreeNode.new(10)
# Test A
# K = 3
# 10
# /
# -5 <- node
node = tree.root.left
tree.distanceKfromNode(node, 3)
# Test B
# K = 3
# 10
# \
# 5
# /
# 7 <- node
node = tree.root.right.left
tree.distanceKfromNode(node, 3)
# Test B
# K = 4
# 10
# \
# 5
# \
# 2 <- node
node = tree.root.right.right
tree.distanceKfromNode(node, 4)
end
main()
Output
Given node -2 and distance K 3
7 2
Given node 7 and distance K 3
10 4 -2
Given node 2 and distance K 4
11 1 3
/*
Scala Program
Print all nodes at distance k from a given node
*/
// 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 result: Boolean,
var count: Int)
{
def this()
{
this(null, false, 0)
}
def printBottomK(track: TreeNode, k: Int): Unit = {
if (track != null)
{
if (k == 0)
{
print(" " + track.data);
this.result = true;
return;
}
printBottomK(track.left, k - 1);
printBottomK(track.right, k - 1);
}
}
def findResult(track: TreeNode, node: TreeNode, k: Int): TreeNode = {
if (track != null && this.count <= k)
{
if (track == node)
{
return track;
}
else
{
var point: TreeNode = findResult(track.left, node, k);
if (point == null)
{
point = findResult(track.right, node, k);
}
if (point != null)
{
this.count += 1;
if (this.count == k)
{
// Current path node
print(" " + track.data);
this.result = true;
}
else if (track.left == point && this.count < k)
{
printBottomK(track.right, k - (this.count + 1));
}
else if (track.right == point && this.count < k)
{
printBottomK(track.left, k - (this.count + 1));
}
return track;
}
}
}
return null;
}
// This function are handle the request of finding
// every k distance node from given node.
def distanceKfromNode(node: TreeNode, k: Int): Unit = {
if (k <= 0 || node == null)
{
return;
}
this.result = false;
this.count = 0;
println("\n Given node " + (node.data) + " and distance K " + k);
// Print bottom element
printBottomK(node, k);
findResult(this.root, node, k);
if (this.result == false)
{
print(" No result \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
Binary Tree
------------
10
/ \
-2 5
/ \ / \
1 3 7 2
/ \ \
9 8 4
/
11
\
10
*/
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(-2);
tree.root.right = new TreeNode(5);
tree.root.right.right = new TreeNode(2);
tree.root.right.right.right = new TreeNode(4);
tree.root.right.left = new TreeNode(7);
tree.root.right.left.right = new TreeNode(8);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(9);
tree.root.right.left.right.left = new TreeNode(11);
tree.root.right.left.right.left.right = new TreeNode(10);
// Test A
// K = 3
// 10
// /
// -5 <- node
var node: TreeNode = tree.root.left;
tree.distanceKfromNode(node, 3);
// Test B
// K = 3
// 10
// \
// 5
// /
// 7 <- node
node = tree.root.right.left;
tree.distanceKfromNode(node, 3);
// Test B
// K = 4
// 10
// \
// 5
// \
// 2 <- node
node = tree.root.right.right;
tree.distanceKfromNode(node, 4);
}
}
Output
Given node -2 and distance K 3
7 2
Given node 7 and distance K 3
10 4 -2
Given node 2 and distance K 4
11 1 3
/*
Swift 4 Program
Print all nodes at distance k from a given node
*/
// 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 result: Bool;
var count: Int;
init()
{
self.root = nil;
self.result = false;
self.count = 0;
}
func printBottomK(_ track: TreeNode? , _ k : Int)
{
if (track != nil)
{
if (k == 0)
{
print(" ", track!.data, terminator: "");
self.result = true;
return;
}
self.printBottomK(track!.left, k - 1);
self.printBottomK(track!.right, k - 1);
}
}
func findResult(_ track: TreeNode? ,
_ node : TreeNode? ,
_ k : Int) -> TreeNode?
{
if (track != nil && self.count <= k)
{
if (track === node)
{
return track;
}
else
{
var point: TreeNode? = self.findResult(track!.left,
node, k);
if (point == nil)
{
point = self.findResult(track!.right, node, k);
}
if (point != nil)
{
self.count += 1;
if (self.count == k)
{
// Current path node
print(" ", track!.data, terminator: "");
self.result = true;
}
else if (track!.left === point && self.count < k)
{
self.printBottomK(track!.right,
k - (self.count + 1));
}
else if (track!.right === point && self.count < k)
{
self.printBottomK(track!.left,
k - (self.count + 1));
}
return track;
}
}
}
return nil;
}
// This function are handle the request of finding
// every k distance node from given node.
func distanceKfromNode(_ node: TreeNode? , _ k : Int)
{
if (k <= 0 || node == nil)
{
return;
}
self.result = false;
self.count = 0;
print("\n Given node ",
(node!.data) ," and distance K ", k);
// Print bottom element
self.printBottomK(node, k);
let _ = self.findResult(self.root, node, k);
if (self.result == false)
{
print(" No result ");
}
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
Binary Tree
------------
10
/ \
-2 5
/ \ / \
1 3 7 2
/ \ \
9 8 4
/
11
\
10
*/
tree.root = TreeNode(10);
tree.root!.left = TreeNode(-2);
tree.root!.right = TreeNode(5);
tree.root!.right!.right = TreeNode(2);
tree.root!.right!.right!.right = TreeNode(4);
tree.root!.right!.left = TreeNode(7);
tree.root!.right!.left!.right = TreeNode(8);
tree.root!.left!.left = TreeNode(1);
tree.root!.left!.right = TreeNode(3);
tree.root!.left!.right!.left = TreeNode(9);
tree.root!.right!.left!.right!.left = TreeNode(11);
tree.root!.right!.left!.right!.left!.right = TreeNode(10);
// Test A
// K = 3
// 10
// /
// -5 <- node
var node: TreeNode? = tree.root!.left;
tree.distanceKfromNode(node, 3);
// Test B
// K = 3
// 10
// \
// 5
// /
// 7 <- node
node = tree.root!.right!.left;
tree.distanceKfromNode(node, 3);
// Test B
// K = 4
// 10
// \
// 5
// \
// 2 <- node
node = tree.root!.right!.right;
tree.distanceKfromNode(node, 4);
}
main();
Output
Given node -2 and distance K 3
7 2
Given node 7 and distance K 3
10 4 -2
Given node 2 and distance K 4
11 1 3
/*
Kotlin Program
Print all nodes at distance k from a given node
*/
// 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 result: Boolean;
var count: Int;
constructor()
{
this.root = null;
this.result = false;
this.count = 0;
}
fun printBottomK(track: TreeNode ? , k : Int): Unit
{
if (track != null)
{
if (k == 0)
{
print(" " + track.data);
this.result = true;
return;
}
this.printBottomK(track.left, k - 1);
this.printBottomK(track.right, k - 1);
}
}
fun findResult(track: TreeNode ? ,
node : TreeNode ? ,
k : Int): TreeNode ?
{
if (track != null && this.count <= k)
{
if (track == node)
{
return track;
}
else
{
var point: TreeNode ? = this.findResult(track.left,
node, k);
if (point == null)
{
point = this.findResult(track.right, node, k);
}
if (point != null)
{
this.count += 1;
if (this.count == k)
{
// Current path node
print(" " + track.data);
this.result = true;
}
else if (track.left == point && this.count < k)
{
this.printBottomK(track.right,
k - (this.count + 1));
}
else if (track.right == point && this.count < k)
{
this.printBottomK(track.left,
k - (this.count + 1));
}
return track;
}
}
}
return null;
}
// This function are handle the request of finding
// every k distance node from given node.
fun distanceKfromNode(node: TreeNode ? , k : Int): Unit
{
if (k <= 0 || node == null)
{
return;
}
this.result = false;
this.count = 0;
println("\n Given node " +
(node.data) + " and distance K " + k);
// Print bottom element
this.printBottomK(node, k);
this.findResult(this.root, node, k);
if (this.result == false)
{
print(" No result \n");
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinaryTree = BinaryTree();
/*
Binary Tree
------------
10
/ \
-2 5
/ \ / \
1 3 7 2
/ \ \
9 8 4
/
11
\
10
*/
tree.root = TreeNode(10);
tree.root?.left = TreeNode(-2);
tree.root?.right = TreeNode(5);
tree.root?.right?.right = TreeNode(2);
tree.root?.right?.right?.right = TreeNode(4);
tree.root?.right?.left = TreeNode(7);
tree.root?.right?.left?.right = TreeNode(8);
tree.root?.left?.left = TreeNode(1);
tree.root?.left?.right = TreeNode(3);
tree.root?.left?.right?.left = TreeNode(9);
tree.root?.right?.left?.right?.left = TreeNode(11);
tree.root?.right?.left?.right?.left?.right = TreeNode(10);
// Test A
// K = 3
// 10
// /
// -5 <- node
var node: TreeNode ? = tree.root?.left;
tree.distanceKfromNode(node, 3);
// Test B
// K = 3
// 10
// \
// 5
// /
// 7 <- node
node = tree.root?.right?.left;
tree.distanceKfromNode(node, 3);
// Test B
// K = 4
// 10
// \
// 5
// \
// 2 <- node
node = tree.root?.right?.right;
tree.distanceKfromNode(node, 4);
}
Output
Given node -2 and distance K 3
7 2
Given node 7 and distance K 3
10 4 -2
Given node 2 and distance K 4
11 1 3
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