Skip to main content

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
Last updated on by Kalkicode




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