Posted on by Kalkicode
Code Hash

Print all nodes that are at distance k from a leaf node

Here given code implementation process.

import java.util.HashSet;
import java.util.ArrayList;
/*
    Java Program
    Print all nodes that are at distance k from a leaf 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 BinaryTree()
	{
		// Set initial value
		this.root = null;
	}
	public void findResult(TreeNode node, 
                            HashSet < TreeNode > result, 
                            ArrayList < TreeNode > path, int k)
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				if (path.size() >= k)
				{
					// Add k distance element
					result.add(path.get(path.size() - k));
				}
				return;
			}
			// Add path node
			path.add(node);
			//  Visit left and right subtree using recursively
			findResult(node.left, result, path, k);
			findResult(node.right, result, path, k);
			// Remove last node in path
			path.remove(path.size() - 1);
		}
	}
	//  Handles the request of finding kth from left node to root
	public void distanceKfromLeft(int k)
	{
		if (k < 0)
		{
			return;
		}
		// This is used to collect unique result
		HashSet < TreeNode > result = new HashSet < TreeNode > ();
		// This is used to track the path from root to leaf node
		ArrayList < TreeNode > path = new ArrayList < TreeNode > ();
		// Find nodes
		findResult(this.root, result, path, k);
		System.out.println("\n Given K " + k);
		if (result.size() == 0)
		{
			// When result not exists
			System.out.print(" No result \n");
		}
		else
		{
			// Display calculated result
			for (TreeNode node: result)
			{
				System.out.print("  " + node.data);
			}
		}
	}
	public static void main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*   
		    Binary Tree
		    ------------
		         10
		       /    \
		      -2     5
		     / \    /  \
		    1   3  7    2
		       /    \    \
		      9      8    4
		            /
		           11 
		*/
		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);
		// Test A
		// K = 2
		tree.distanceKfromLeft(2);
		// Test B
		// K = 4
		tree.distanceKfromLeft(4);
		// Test C
		// K = 1
		tree.distanceKfromLeft(1);
		// Test D
		// K = 3
		tree.distanceKfromLeft(3);
	}
}

Output

 Given K 2
  5  10  -2  7
 Given K 4
  10
 Given K 1
  2  8  -2  3
 Given K 3
  5  10
// Include header file
#include <iostream>
#include <set>
#include <vector>

using namespace std;
/*
    C++ Program
    Print all nodes that are at distance k from a leaf 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;
    BinaryTree()
    {
        this->root = NULL;
    }
    void findResult(TreeNode *node, 
                    set < TreeNode*> &result, 
                    vector < TreeNode *> &path, int k)
    {
        if (node != NULL)
        {
            if (node->left == NULL && node->right == NULL)
            {
                if (path.size() >= k)
                {
                    // Add k distance element
                    result.insert(path.at(path.size() - k));
                }
                return;
            }
            // Add path node
            path.push_back(node);
            //  Visit left and right subtree using recursively
            this->findResult(node->left, result, path, k);
            this->findResult(node->right, result, path, k);
            // Remove last node in path
            path.pop_back();
        }
    }
    //  Handles the request of finding kth from left node to root
    void distanceKfromLeft(int k)
    {
        if (k < 0)
        {
            return;
        }
        // This is used to collect unique result
        set < TreeNode *> result;
        // This is used to track the path from root to leaf node
        vector < TreeNode *> path;
        // Find nodes
        this->findResult(this->root, result, path, k);
        cout << "\n Given K " << k << endl;
        if (result.size() == 0)
        {
            // When result not exists
            cout << " No result \n";
        }
        else
        {
            // Display calculated result
            for (auto &v : result)
            {
                cout << "  " << v->data;
            }
        }
    }
};
int main()
{
    BinaryTree *tree = new BinaryTree();
    /* 
        Binary Tree
        ------------
             10
           /    \
          -2     5
         / \    /  \
        1   3  7    2
           /    \    \
          9      8    4
                /
               11 
    */
    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);
    // Test A
    // K = 2
    tree->distanceKfromLeft(2);
    // Test B
    // K = 4
    tree->distanceKfromLeft(4);
    // Test C
    // K = 1
    tree->distanceKfromLeft(1);
    // Test D
    // K = 3
    tree->distanceKfromLeft(3);
    return 0;
}

Output

 Given K 2
  10  -2  5  7
 Given K 4
  10
 Given K 1
  -2  2  8  3
 Given K 3
  10  5
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp Program
    Print all nodes that are at distance k from a leaf 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 BinaryTree()
	{
		// Set initial value
		this.root = null;
	}
	public void findResult(TreeNode node, 
                            HashSet < TreeNode > result, 
                            List < TreeNode > path, int k)
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				if (path.Count >= k)
				{
					// Add k distance element
					result.Add(path[path.Count - k]);
				}
				return;
			}
			// Add path node
			path.Add(node);
			//  Visit left and right subtree using recursively
			this.findResult(node.left, result, path, k);
			this.findResult(node.right, result, path, k);
			// Remove last node in path
			path.RemoveAt(path.Count - 1);
		}
	}
	//  Handles the request of finding kth from left node to root
	public void distanceKfromLeft(int k)
	{
		if (k < 0)
		{
			return;
		}
		// This is used to collect unique result
		HashSet < TreeNode > result = new HashSet < TreeNode > ();
		// This is used to track the path from root to leaf node
		List < TreeNode > path = new List < TreeNode > ();
		// Find nodes
		this.findResult(this.root, result, path, k);
		Console.WriteLine("\n Given K " + k);
		if (result.Count == 0)
		{
			// When result not exists
			Console.Write(" No result \n");
		}
		else
		{
			// Display calculated result
			foreach(TreeNode node in result)
			{
				Console.Write("  " + node.data);
			}
		}
	}
	public static void Main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		    Binary Tree
		    ------------
		         10
		       /    \
		      -2     5
		     / \    /  \
		    1   3  7    2
		       /    \    \
		      9      8    4
		            /
		           11 
		*/
		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);
		// Test A
		// K = 2
		tree.distanceKfromLeft(2);
		// Test B
		// K = 4
		tree.distanceKfromLeft(4);
		// Test C
		// K = 1
		tree.distanceKfromLeft(1);
		// Test D
		// K = 3
		tree.distanceKfromLeft(3);
	}
}

Output

 Given K 2
  10  -2  7  5
 Given K 4
  10
 Given K 1
  -2  3  8  2
 Given K 3
  10  5
package main
import "fmt"
/*
    Go Program
    Print all nodes that are at distance k from a leaf 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
}
func getBinaryTree() * BinaryTree {
	var me *BinaryTree = &BinaryTree {}
	// Set initial value
	me.root = nil
	return me
}
func(this BinaryTree) findResult(node * TreeNode, 
	result map[*TreeNode] bool, path [] *TreeNode , k int) {
	if node != nil {
		if node.left == nil && node.right == nil {
			if len(path) >= k {
				// Add k distance element
				result[path[len(path) - k]] = true
			}
			return
		}
		// Add path node
		path = append(path, node)
		//  Visit left and right subtree using recursively
		this.findResult(node.left, result, path, k)
		this.findResult(node.right, result, path, k)
		// Remove last node in path
		path = append(path[: len(path) - 1], path[len(path) - 1 + 1: ]...)
	}
}
//  Handles the request of finding kth from left node to root
func(this BinaryTree) distanceKfromLeft(k int) {
	if k < 0 {
		return
	}
	// This is used to collect unique result
	var result = make(map[*TreeNode] bool)
	// This is used to track the path from root to leaf node
	var path = make([] *TreeNode, 0)
	// Find nodes
	this.findResult(this.root, result, path, k)
	fmt.Println("\n Given K ", k)
	if len(result) == 0 {
		// When result not exists
		fmt.Print(" No result \n")
	} else {
		// Display calculated result
		for node := range result {
			fmt.Print("  ", node.data)
		}
	}
}
func main() {
	var tree * BinaryTree = getBinaryTree()
	/*
	    Binary Tree
	    ------------
	         10
	       /    \
	      -2     5
	     / \    /  \
	    1   3  7    2
	       /    \    \
	      9      8    4
	            /
	           11 
	*/
	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)
	// Test A
	// K = 2
	tree.distanceKfromLeft(2)
	// Test B
	// K = 4
	tree.distanceKfromLeft(4)
	// Test C
	// K = 1
	tree.distanceKfromLeft(1)
	// Test D
	// K = 3
	tree.distanceKfromLeft(3)
}

Output

 Given K 2
  10  -2  7  5
 Given K 4
  10
 Given K 1
  -2  3  8  2
 Given K 3
  10  5
<?php
/*
    Php Program
    Print all nodes that are at distance k from a leaf 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	function __construct()
	{
		$this->root = NULL;
	}
	public	function findResult($node, &$result, &$path, $k)
	{
		if ($node != NULL)
		{
			if ($node->left == NULL && $node->right == NULL)
			{
				if (count($path) >= $k)
				{
					// Add k distance element
					if (in_array($path[count($path) - $k], $result) == False)
					{
						$result[] = $path[count($path) - $k];
					}
				}
				return;
			}
			// Add path node
			$path[] = $node;
			//  Visit left and right subtree using recursively
			$this->findResult($node->left, $result, $path, $k);
			$this->findResult($node->right, $result, $path, $k);
			// Remove last node in path
			array_pop($path);
		}
	}
	//  Handles the request of finding kth from left node to root
	public	function distanceKfromLeft($k)
	{
		if ($k < 0)
		{
			return;
		}
		// This is used to collect unique result
		$result = array();
		// This is used to track the path from root to leaf node
		$path = array();
		// Find nodes
		$this->findResult($this->root, $result, $path, $k);
		echo("\n Given K ".$k.
			"\n");
		if (count($result) == 0)
		{
			// When result not exists
			echo(" No result \n");
		}
		else
		{
			// Display calculated result
			foreach($result as $p => $node)
			{
				echo("  ".$node->data);
			}
		}
	}
}

function main()
{
	$tree = new BinaryTree();
	/*
	    Binary Tree
	    ------------
	         10
	       /    \
	      -2     5
	     / \    /  \
	    1   3  7    2
	       /    \    \
	      9      8    4
	            /
	           11 
	*/
	$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);
	// Test A
	// K = 2
	$tree->distanceKfromLeft(2);
	// Test B
	// K = 4
	$tree->distanceKfromLeft(4);
	// Test C
	// K = 1
	$tree->distanceKfromLeft(1);
	// Test D
	// K = 3
	$tree->distanceKfromLeft(3);
}
main();

Output

 Given K 2
  10  -2  7  5
 Given K 4
  10
 Given K 1
  -2  3  8  2
 Given K 3
  10  5
/*
    Node JS Program
    Print all nodes that are at distance k from a leaf 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;
	}
	findResult(node, result, path, k)
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				if (path.length >= k)
				{
					// Add k distance element
					result.add(path[path.length - k]);
				}
				return;
			}
			// Add path node
			path.push(node);
			//  Visit left and right subtree using recursively
			this.findResult(node.left, result, path, k);
			this.findResult(node.right, result, path, k);
			// Remove last node in path
			path.pop();
		}
	}
	//  Handles the request of finding kth from left node to root
	distanceKfromLeft(k)
	{
		if (k < 0)
		{
			return;
		}
		// This is used to collect unique result
		var result = new Set();
		// This is used to track the path from root to leaf node
		var path = [];
		// Find nodes
		this.findResult(this.root, result, path, k);
		console.log("\n Given K " + k);
		if (result.size == 0)
		{
			// When result not exists
			process.stdout.write(" No result \n");
		}
		else
		{
			// Display calculated result
			for (let node of result)
			{
				process.stdout.write("  " + node.data);
			}
		}
	}
}

function main()
{
	var tree = new BinaryTree();
	/*
	    Binary Tree
	    ------------
	         10
	       /    \
	      -2     5
	     / \    /  \
	    1   3  7    2
	       /    \    \
	      9      8    4
	            /
	           11 
	*/
	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);
	// Test A
	// K = 2
	tree.distanceKfromLeft(2);
	// Test B
	// K = 4
	tree.distanceKfromLeft(4);
	// Test C
	// K = 1
	tree.distanceKfromLeft(1);
	// Test D
	// K = 3
	tree.distanceKfromLeft(3);
}
main();

Output

 Given K 2
  10  -2  7  5
 Given K 4
  10
 Given K 1
  -2  3  8  2
 Given K 3
  10  5
#    Python 3 Program
#    Print all nodes that are at distance k from a leaf 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
	
	def findResult(self, node, result, path, k) :
		if (node != None) :
			if (node.left == None and node.right == None) :
				if (len(path) >= k) :
					#  Add k distance element
					result.add(path[len(path) - k])
				
				return
			
			#  Add path node
			path.append(node)
			#   Visit left and right subtree using recursively
			self.findResult(node.left, result, path, k)
			self.findResult(node.right, result, path, k)
			#  Remove last node in path
			del path[len(path) - 1]
		
	
	#   Handles the request of finding kth from left node to root
	def distanceKfromLeft(self, k) :
		if (k < 0) :
			return
		
		#  This is used to collect unique result
		result = set()
		#  This is used to track the path from root to leaf node
		path = []
		#  Find nodes
		self.findResult(self.root, result, path, k)
		print("\n Given K ", k)
		if (len(result) == 0) :
			#  When result not exists
			print(" No result ")
		else :
			for node in result :
				print("  ", node.data, end = "")
			
		
	

def main() :
	tree = BinaryTree()
	#    Binary Tree
	#    ------------
	#         10
	#       /    \
	#      -2     5
	#     / \    /  \
	#    1   3  7    2
	#       /    \    \
	#      9      8    4
	#            /
	#           11 
	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)
	#  Test A
	#  K = 2
	tree.distanceKfromLeft(2)
	#  Test B
	#  K = 4
	tree.distanceKfromLeft(4)
	#  Test C
	#  K = 1
	tree.distanceKfromLeft(1)
	#  Test D
	#  K = 3
	tree.distanceKfromLeft(3)

if __name__ == "__main__": main()

Output

 Given K  2
   5   10   7   -2
 Given K  4
   10
 Given K  1
   3   8   2   -2
 Given K  3
   5   10
#    Ruby Program
#    Print all nodes that are at distance k from a leaf 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
	attr_accessor :root
	def initialize() 
		self.root = nil
	end

	def findResult(node, result, path, k) 
		if (node != nil) 
			if (node.left == nil && node.right == nil) 
				if (path.length >= k ) 
                  	result.delete(path[path.length - k])
					#  Add k distance element
					result.push(path[path.length - k])
				end

				return
			end

			#  Add path node
			path.push(node)
			#  Visit left and right subtree using recursively
			self.findResult(node.left, result, path, k)
			self.findResult(node.right, result, path, k)
			#  Remove last node in path
			path.delete_at(path.length - 1)
		end

	end

	#   Handles the request of finding kth from left node to root
	def distanceKfromLeft(k) 
		if (k < 0) 
			return
		end

		#  This is used to collect unique result
		result = []
		#  This is used to track the path from root to leaf node
		path = []
		#  Find nodes
		self.findResult(self.root, result, path, k)
		print("\n Given K ", k, "\n")
		if (result.size() == 0) 
			#  When result not exists
			print(" No result \n")
		else
 
			#  Display calculated result
			result.each do  | node |
				print("  ", node.data)
            end

		end

	end

end

def main() 
	tree = BinaryTree.new()
	#    Binary Tree
	#    ------------
	#         10
	#       /    \
	#      -2     5
	#     / \    /  \
	#    1   3  7    2
	#       /    \    \
	#      9      8    4
	#            /
	#           11 
	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)
	#  Test A
	#  K = 2
	tree.distanceKfromLeft(2)
	#  Test B
	#  K = 4
	tree.distanceKfromLeft(4)
	#  Test C
	#  K = 1
	tree.distanceKfromLeft(1)
	#  Test D
	#  K = 3
	tree.distanceKfromLeft(3)
end

main()

Output

 Given K 2
  10  -2  7  5
 Given K 4
  10
 Given K 1
  -2  3  8  2
 Given K 3
  5  10
import scala.collection.mutable._;
/*
    Scala Program
    Print all nodes that are at distance k from a leaf 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)
{
	def this()
	{

		this(null)
	}
	def findResult(
      node: TreeNode, 
      result: Set[TreeNode], 
      path: ArrayBuffer[TreeNode], 
        k: Int): Unit = {
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				if (path.size >= k)
				{
					// Add k distance element
					result.add(path(path.size - k));
				}
				return;
			}
			// Add path node
			path += node;
			//  Visit left and right subtree using recursively
			findResult(node.left, result, path, k);
			findResult(node.right, result, path, k);
			// Remove last node in path
			path.remove(path.size - 1);
		}
	}
	//  Handles the request of finding kth from left node to root
	def distanceKfromLeft(k: Int): Unit = {
		if (k < 0)
		{
			return;
		}
		// This is used to collect unique result
		var result: Set[TreeNode] =  Set();
		// This is used to track the path from root to leaf node
		var path: ArrayBuffer[TreeNode] = 
          new ArrayBuffer[TreeNode]();
		// Find nodes
		findResult(this.root, result, path, k);
		println("\n Given K " + k);
		if (result.size == 0)
		{
			// When result not exists
			print(" No result \n");
		}
		else
		{
			// Display calculated result
			for ((node) <- result)
			{
				print("  " + node.data);
			}
		}
	}
}
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 
		*/
		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);
		// Test A
		// K = 2
		tree.distanceKfromLeft(2);
		// Test B
		// K = 4
		tree.distanceKfromLeft(4);
		// Test C
		// K = 1
		tree.distanceKfromLeft(1);
		// Test D
		// K = 3
		tree.distanceKfromLeft(3);
	}
}

Output

 Given K 2
  7  10  -2  5
 Given K 4
  10
 Given K 1
  3  -2  2  8
 Given K 3
  10  5
/*
    Kotlin Program
    Print all nodes that are at distance k from a leaf 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 ? ;
	constructor()
	{
		this.root = null;
	}
	fun findResult(node: TreeNode ? , 
                   result : MutableSet< TreeNode >  , 
                   path : MutableList < TreeNode >  , k : Int): Unit
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				if (path.size >= k)
				{
					// Add k distance element
					result.add(path[path.size - k]);
				}
				return;
			}
			// Add path node
			path.add(node);
			//  Visit left and right subtree using recursively
			this.findResult(node.left, result, path, k);
			this.findResult(node.right, result, path, k);
			// Remove last node in path
			path.removeAt(path.size - 1);
		}
	}
	//  Handles the request of finding kth from left node to root
	fun distanceKfromLeft(k: Int): Unit
	{
		if (k < 0)
		{
			return;
		}
		// This is used to collect unique result
		val result: MutableSet< TreeNode > = mutableSetOf< TreeNode > ();
		// This is used to track the path from root to leaf node
		val path: MutableList < TreeNode > = mutableListOf < TreeNode > ();
		// Find nodes
		this.findResult(this.root, result, path, k);
		println("\n Given K " + k);
		if (result.count() == 0)
		{
			// When result not exists
			print(" No result \n");
		}
		else
		{
			// Display calculated result
			for (node in result)
			{
				print("  " + node.data);
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val tree: BinaryTree = BinaryTree();
	/*
	    Binary Tree
	    ------------
	         10
	       /    \
	      -2     5
	     / \    /  \
	    1   3  7    2
	       /    \    \
	      9      8    4
	            /
	           11 
	*/
	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);
	// Test A
	// K = 2
	tree.distanceKfromLeft(2);
	// Test B
	// K = 4
	tree.distanceKfromLeft(4);
	// Test C
	// K = 1
	tree.distanceKfromLeft(1);
	// Test D
	// K = 3
	tree.distanceKfromLeft(3);
}

Output

 Given K 2
  10  -2  7  5
 Given K 4
  10
 Given K 1
  -2  3  8  2
 Given K 3
  10  5

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.

New Comment





Categories
Relative Post