Find the length of each path in binary tree
Here given code implementation process.
/*
Java Program
Find the length of each path in binary tree
*/
import java.util.HashMap;
import java.util.Map;
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()
{
this.root = null;
}
// Find all path from root to leaf node
public void findPath(TreeNode node, HashMap < Integer, Integer > record, int length)
{
if (node == null)
{
return;
}
else
{
// Recursively visit left and right subtree
findPath(node.left, record, length + 1);
findPath(node.right, record, length + 1);
if (node.left == null && node.right == null)
{
// When get leaf node
// Check path length exist or not
if (record.containsKey(length))
{
record.put(length, record.get(length) + 1);
}
else
{
// Add new length
record.put(length, 1);
}
}
}
}
public void pathLength()
{
if (this.root == null)
{
System.out.print("Empty Tree\n");
return;
}
// Use to collect information of collecting path length
HashMap < Integer, Integer > record =
new HashMap < Integer, Integer > ();
findPath(this.root, record, 1);
// Print calculated result
for (Map.Entry < Integer, Integer > result: record.entrySet())
{
System.out.print("\n Path of length " + result.getKey() +
" is : " + result.getValue());
}
}
public static void main(String[] arg)
{
BinaryTree tree = new BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 8
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(8);
tree.pathLength();
}
}
Output
Path of length 3 is : 1
Path of length 4 is : 1
Path of length 5 is : 3
// Include header file
#include <iostream>
#include <unordered_map>
using namespace std;
/*
C++ Program
Find the length of each path in binary tree
*/
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;
}
// Find all path from root to leaf node
void findPath(TreeNode *node, unordered_map < int, int > &record, int length)
{
if (node == NULL)
{
return;
}
else
{
// Recursively visit left and right subtree
this->findPath(node->left, record, length + 1);
this->findPath(node->right, record, length + 1);
if (node->left == NULL && node->right == NULL)
{
// When get leaf node
// Check path length exist or not
if (record.find(length) != record.end())
{
record[length] = record[length] + 1;
}
else
{
// Add new length
record[length] = 1;
}
}
}
}
void pathLength()
{
if (this->root == NULL)
{
cout << "Empty Tree\n";
return;
}
// Use to collect information of collecting path length
unordered_map < int, int > record ;
this->findPath(this->root, record, 1);
unordered_map <int, int> ::iterator result;
for (result = record.begin(); result != record.end(); result++)
{
cout << "\n Path of length " << result->first << " is : "
<< result->second;
}
}
};
int main()
{
BinaryTree tree = BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 8
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root->left = new TreeNode(2);
tree.root->right = new TreeNode(3);
tree.root->left->left = new TreeNode(3);
tree.root->left->right = new TreeNode(4);
tree.root->left->right->left = new TreeNode(-7);
tree.root->left->right->left->left = new TreeNode(9);
tree.root->right->left = new TreeNode(6);
tree.root->right->right = new TreeNode(5);
tree.root->right->left->right = new TreeNode(4);
tree.root->right->right->right = new TreeNode(2);
tree.root->right->left->right->left = new TreeNode(1);
tree.root->right->left->right->right = new TreeNode(8);
tree.pathLength();
return 0;
}
Output
Path of length 4 is : 1
Path of length 5 is : 3
Path of length 3 is : 1
// Include namespace system
using System;
using System.Collections.Generic;
/*
C# Program
Find the length of each path in binary tree
*/
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()
{
this.root = null;
}
// Find all path from root to leaf node
public void findPath(TreeNode node, Dictionary < int, int > record, int length)
{
if (node == null)
{
return;
}
else
{
// Recursively visit left and right subtree
findPath(node.left, record, length + 1);
findPath(node.right, record, length + 1);
if (node.left == null && node.right == null)
{
// When get leaf node
// Check path length exist or not
if (record.ContainsKey(length))
{
record[length] = record[length] + 1;
}
else
{
// Add new length
record.Add(length, 1);
}
}
}
}
public void pathLength()
{
if (this.root == null)
{
Console.Write("Empty Tree\n");
return;
}
// Use to collect information of collecting path length
Dictionary < int, int > record = new Dictionary < int, int > ();
findPath(this.root, record, 1);
foreach(KeyValuePair < int, int > result in record)
{
Console.Write("\n Path of length " + result.Key + " is : "
+ result.Value);
}
}
public static void Main(String[] arg)
{
BinaryTree tree = new BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 8
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(8);
tree.pathLength();
}
}
Output
Path of length 3 is : 1
Path of length 5 is : 3
Path of length 4 is : 1
<?php
/*
Php Program
Find the length of each path in binary tree
*/
class TreeNode
{
public $data;
public $left;
public $right;
function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
class BinaryTree
{
public $root;
function __construct()
{
$this->root = null;
}
// Find all path from root to leaf node
public function findPath($node, &$record, $length)
{
if ($node == null)
{
return;
}
else
{
// Recursively visit left and right subtree
$this->findPath($node->left, $record, $length + 1);
$this->findPath($node->right, $record, $length + 1);
if ($node->left == null && $node->right == null)
{
// When get leaf node
// Check path length exist or not
if (array_key_exists($length, $record))
{
$record[$length] = $record[$length] + 1;
}
else
{
$record[$length] = 1;
}
}
}
}
public function pathLength()
{
if ($this->root == null)
{
echo "Empty Tree\n";
return;
}
// Use to collect information of collecting path length
$record = array();
$this->findPath($this->root, $record, 1);
foreach($record as $key => $value)
{
echo "\n Path of length ". $key ." is : ".
$value;
}
}
}
function main()
{
$tree = new BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 8
-----------------------
Binary Tree
-----------------------
*/
$tree->root = new TreeNode(1);
$tree->root->left = new TreeNode(2);
$tree->root->right = new TreeNode(3);
$tree->root->left->left = new TreeNode(3);
$tree->root->left->right = new TreeNode(4);
$tree->root->left->right->left = new TreeNode(-7);
$tree->root->left->right->left->left = new TreeNode(9);
$tree->root->right->left = new TreeNode(6);
$tree->root->right->right = new TreeNode(5);
$tree->root->right->left->right = new TreeNode(4);
$tree->root->right->right->right = new TreeNode(2);
$tree->root->right->left->right->left = new TreeNode(1);
$tree->root->right->left->right->right = new TreeNode(8);
$tree->pathLength();
}
main();
Output
Path of length 3 is : 1
Path of length 5 is : 3
Path of length 4 is : 1
/*
Node Js Program
Find the length of each path in binary tree
*/
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
// Find all path from root to leaf node
findPath(node, record, length)
{
if (node == null)
{
return;
}
else
{
// Recursively visit left and right subtree
this.findPath(node.left, record, length + 1);
this.findPath(node.right, record, length + 1);
if (node.left == null && node.right == null)
{
// When get leaf node
// Check path length exist or not
if (record.has(length))
{
record.set(length, record.get(length) + 1);
}
else
{
// Add new length
record.set(length, 1);
}
}
}
}
pathLength()
{
if (this.root == null)
{
process.stdout.write("Empty Tree\n");
return;
}
// Use to collect information of collecting path length
var record = new Map();
this.findPath(this.root, record, 1);
for (let [key, value] of record)
{
console.log(" Path of length " + key + " is : "
+ value);
}
}
}
function main()
{
var tree = new BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 8
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(8);
tree.pathLength();
}
main();
Output
Path of length 3 is : 1
Path of length 5 is : 3
Path of length 4 is : 1
# Python 3 Program
# Find the length of each path in binary tree
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
# Find all path from root to leaf node
def findPath(self, node,record, length) :
if (node == None) :
return
else :
# Recursively visit left and right subtree
self.findPath(node.left, record, length + 1)
self.findPath(node.right, record, length + 1)
if (node.left == None and node.right == None) :
# When get leaf node
# Check path length exist or not
if (length in record.keys()) :
record[length] = record.get(length) + 1
else :
# Add new length
record[length] = 1
def pathLength(self) :
if (self.root == None) :
print("Empty Tree")
return
# Use to collect information of collecting path length
record = dict()
self.findPath(self.root, record, 1)
for key, value in record.items():
print("\n Path of length ", key ," is : ",
value, end = "")
def main() :
tree = BinaryTree()
#
# 1
# / \
# 2 3
# / \ / \
# 3 4 6 5
# / \ \
# -7 4 2
# / / \
# 9 1 8
# -----------------------
# Binary Tree
# -----------------------
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.left.left = TreeNode(3)
tree.root.left.right = TreeNode(4)
tree.root.left.right.left = TreeNode(-7)
tree.root.left.right.left.left = TreeNode(9)
tree.root.right.left = TreeNode(6)
tree.root.right.right = TreeNode(5)
tree.root.right.left.right = TreeNode(4)
tree.root.right.right.right = TreeNode(2)
tree.root.right.left.right.left = TreeNode(1)
tree.root.right.left.right.right = TreeNode(8)
tree.pathLength()
if __name__ == "__main__": main()
Output
Path of length 3 is : 1
Path of length 4 is : 1
Path of length 5 is : 3
# Ruby Program
# Find the length of each path in binary tree
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
# Find all path from root to leaf node
def findPath(node, record, length)
if (node == nil)
return
else
# Recursively visit left and right subtree
self.findPath(node.left, record, length + 1)
self.findPath(node.right, record, length + 1)
if (node.left == nil && node.right == nil)
# When get leaf node
# Check path length exist or not
if (record.key?(length))
record[length] = record[length] + 1
else
record[length] = 1
end
end
end
end
def pathLength()
if (self.root == nil)
print("Empty Tree\n")
return
end
# Use to collect information of collecting path length
record = Hash.new
self.findPath(self.root, record, 1)
record.each{ |key,value|
print("\n Path of length ", key ," is : ",
value)
}
end
end
def main()
tree = BinaryTree.new()
#
# 1
# / \
# 2 3
# / \ / \
# 3 4 6 5
# / \ \
# -7 4 2
# / / \
# 9 1 8
# -----------------------
# Binary Tree
# -----------------------
tree.root = TreeNode.new(1)
tree.root.left = TreeNode.new(2)
tree.root.right = TreeNode.new(3)
tree.root.left.left = TreeNode.new(3)
tree.root.left.right = TreeNode.new(4)
tree.root.left.right.left = TreeNode.new(-7)
tree.root.left.right.left.left = TreeNode.new(9)
tree.root.right.left = TreeNode.new(6)
tree.root.right.right = TreeNode.new(5)
tree.root.right.left.right = TreeNode.new(4)
tree.root.right.right.right = TreeNode.new(2)
tree.root.right.left.right.left = TreeNode.new(1)
tree.root.right.left.right.right = TreeNode.new(8)
tree.pathLength()
end
main()
Output
Path of length 3 is : 1
Path of length 5 is : 3
Path of length 4 is : 1
import scala.collection.mutable._;
/*
Scala Program
Find the length of each path in binary tree
*/
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Find all path from root to leaf node
def findPath(node: TreeNode, record: Map[Int, Int], length: Int): Unit = {
if (node == null)
{
return;
}
else
{
// Recursively visit left and right subtree
this.findPath(node.left, record, length + 1);
this.findPath(node.right, record, length + 1);
if (node.left == null && node.right == null)
{
// When get leaf node
// Check path length exist or not
if (record.contains(length))
{
record.addOne(length, record.get(length).get + 1);
}
else
{
// Add new length
record.addOne(length, 1);
}
}
}
}
def pathLength(): Unit = {
if (this.root == null)
{
print("Empty Tree\n");
return;
}
// Use to collect information of collecting path length
var record: Map[Int, Int] = Map();
this.findPath(this.root, record, 1);
record.keys.foreach
{
key =>
print("\n Path of length " +key + " is : " + record(key));
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 8
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(8);
tree.pathLength();
}
}
Output
Path of length 3 is : 1
Path of length 4 is : 1
Path of length 5 is : 3
import Foundation
/*
Swift 4 Program
Find the length of each path in binary tree
*/
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? ;
init()
{
self.root = nil;
}
// Find all path from root to leaf node
func findPath(_ node: TreeNode? ,_ record : inout[Int: Int], _ length: Int)
{
if (node == nil)
{
return;
}
else
{
// Recursively visit left and right subtree
self.findPath(node!.left, &record, length + 1);
self.findPath(node!.right, &record, length + 1);
if (node!.left == nil && node!.right == nil)
{
// When get leaf node
// Check path length exist or not
if (record.keys.contains(length))
{
record[length] = record[length]! + 1;
}
else
{
// Add new length
record[length] = 1;
}
}
}
}
func pathLength()
{
if (self.root == nil)
{
print("Empty Tree");
return;
}
// Use to collect information of collecting path length
var record = [Int: Int]();
self.findPath(self.root, &record, 1);
for (key,value) in record
{
print("\n Path of length ", key ," is : ",
value, terminator: "");
}
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 8
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root!.left = TreeNode(2);
tree.root!.right = TreeNode(3);
tree.root!.left!.left = TreeNode(3);
tree.root!.left!.right = TreeNode(4);
tree.root!.left!.right!.left = TreeNode(-7);
tree.root!.left!.right!.left!.left = TreeNode(9);
tree.root!.right!.left = TreeNode(6);
tree.root!.right!.right = TreeNode(5);
tree.root!.right!.left!.right = TreeNode(4);
tree.root!.right!.right!.right = TreeNode(2);
tree.root!.right!.left!.right!.left = TreeNode(1);
tree.root!.right!.left!.right!.right = TreeNode(8);
tree.pathLength();
}
main();
Output
Path of length 5 is : 3
Path of length 3 is : 1
Path of length 4 is : 1
/*
Kotlin Program
Find the length of each path in binary tree
*/
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;
}
// Find all path from root to leaf node
fun findPath(node: TreeNode? , record : HashMap < Int, Int > , length : Int): Unit
{
if (node == null)
{
return;
}
else
{
// Recursively visit left and right subtree
this.findPath(node.left, record, length + 1);
this.findPath(node.right, record, length + 1);
if (node.left == null && node.right == null)
{
// When get leaf node
// Check path length exist or not
if (record.containsKey(length))
{
record.put(length, record[length]!! + 1);
}
else
{
// Add new length
record.put(length, 1);
}
}
}
}
fun pathLength(): Unit
{
if (this.root == null)
{
print("Empty Tree\n");
return;
}
// Use to collect information of collecting path length
var record = hashMapOf < Int , Int > ();
this.findPath(this.root, record, 1);
// Print calculated result
for (key in record.keys)
{
print("\n Path of length " + key + " is : " + record[key]);
}
}
}
fun main(args: Array < String > ): Unit
{
var tree: BinaryTree = BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 8
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root?.left = TreeNode(2);
tree.root?.right = TreeNode(3);
tree.root?.left?.left = TreeNode(3);
tree.root?.left?.right = TreeNode(4);
tree.root?.left?.right?.left = TreeNode(-7);
tree.root?.left?.right?.left?.left = TreeNode(9);
tree.root?.right?.left = TreeNode(6);
tree.root?.right?.right = TreeNode(5);
tree.root?.right?.left?.right = TreeNode(4);
tree.root?.right?.right?.right = TreeNode(2);
tree.root?.right?.left?.right?.left = TreeNode(1);
tree.root?.right?.left?.right?.right = TreeNode(8);
tree.pathLength();
}
Output
Path of length 3 is : 1
Path of length 4 is : 1
Path of length 5 is : 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