Posted on by Kalkicode
Code Recursion

Find length of longest straight path from a given binary tree

Find the length of the longest path of consecutive nodes in a binary tree that are either all left or all right.

In other words, given a binary tree, we want to find the length of the longest sequence of nodes that form a straight path either to the left or to the right, where each node in the sequence has either all left or all right children (if any children at all).

Program Solution

// C program
// Find length of longest straight path from a given binary tree
#include <stdio.h>
#include <stdlib.h>

 // Tree Node
struct TreeNode
{
	int data;
	struct TreeNode *left;
	struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
	struct TreeNode *root;
};
// Create new tree
struct BinaryTree *newTree()
{
	// Create dynamic node
	struct BinaryTree *tree = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
	if (tree != NULL)
	{
		tree->root = NULL;
	}
	else
	{
		printf("Memory Overflow to Create tree Tree\n");
	}
	// return new tree
	return tree;
}
// This is creates and returns the new binary tree node
struct TreeNode *getNode(int data)
{
	// Create dynamic node
	struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		// Set data and pointer values
		node->data = data;
		node->left = NULL;
		node->right = NULL;
	}
	else
	{
		// This is indicates, segmentation fault or 
		// memory overflow problem
		printf("Memory Overflow\n");
	}
	// return new node
	return node;
}
// Find the length of longest straight path in binary tree
void longestStraightPath(struct TreeNode *node, struct TreeNode *parent, int direction, int *result)
{
	if (node == NULL)
	{
		return;
	}
	if (parent == NULL)
	{
		// First node of tree
		// Here 1 indicate if next node exist then straight path will be 1
		longestStraightPath(node->left, node, 1, result);
		longestStraightPath(node->right, node, 1, result);
	}
	else
	{
		if (direction > *result)
		{
			// Get new result
			*result = direction;
		}
		if (parent->left == node)
		{
			// Current node exists in left side of parent
			longestStraightPath(node->left, node, direction + 1, result);
			longestStraightPath(node->right, node, 1, result);
		}
		else
		{
			// Current node exists in right side of parent
			longestStraightPath(node->left, node, 1, result);
			longestStraightPath(node->right, node, direction + 1, result);
		}
	}
}
void straightPath(struct TreeNode *node)
{
	int result = 0;
	longestStraightPath(node, NULL, 0, & result);
	// Display the calculated result 
	printf("\n Longest straight path : %d", result);
}
int main(int argc, char
	const *argv[])
{
	struct BinaryTree *tree = newTree();
	/*
	             4                            
	           /   \    
	         -4     7    
	         / \     \               
	        2   3     12
	           / \    / 
	          10  8  5
	          /    \  \
	         9      1   12 

	    -----------------
	    Constructing binary tree

	*/
	tree->root = getNode(4);
	tree->root->left = getNode(-4);
	tree->root->left->right = getNode(3);
	tree->root->left->right->left = getNode(10);
	tree->root->left->right->left->left = getNode(9);
	tree->root->left->right->right = getNode(8);
	tree->root->left->right->right->right = getNode(1);
	tree->root->left->left = getNode(2);
	tree->root->right = getNode(7);
	tree->root->right->right = getNode(12);
	tree->root->right->right->left = getNode(5);
	tree->root->right->right->left->right = getNode(5);
	straightPath(tree->root);
	return 0;
}

input

 Longest straight path : 3
/*
    Java Program
    Print nodes at k distance from root
*/
// Binary Tree node
class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public int result;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
		this.result = 0;
	}
	// Find the length of longest straight path in binary tree
	public void longestStraightPath(TreeNode node, TreeNode parent, int direction)
	{
		if (node == null)
		{
			return;
		}
		if (parent == null)
		{
			// First node of tree
			// Here 1 indicate if next node exist then straight path will be 1
			longestStraightPath(node.left, node, 1);
			longestStraightPath(node.right, node, 1);
		}
		else
		{
			if (direction > this.result)
			{
				// Get new result
				this.result = direction;
			}
			if (parent.left == node)
			{
				// Current node exists in left side of parent
				longestStraightPath(node.left, node, direction + 1);
				longestStraightPath(node.right, node, 1);
			}
			else
			{
				// Current node exists in right side of parent
				longestStraightPath(node.left, node, 1);
				longestStraightPath(node.right, node, direction + 1);
			}
		}
	}
	// Handles the request of finding longest straight path in tree
	public void straightPath()
	{
		this.result = 0;
		longestStraightPath(this.root, null, 0);
		// Display the calculated result
		System.out.print("\n Longest straight path : " + this.result);
	}
	public static void main(String[] args)
	{
		// Create new binary tree
		BinaryTree tree = new BinaryTree();
		/*
		         4                            
		       /   \    
		     -4     7    
		     / \     \               
		    2   3     12
		       / \    / 
		      10  8  5
		      /    \  \
		     9      1   12 
		-----------------
		Constructing binary tree
		                
		        
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(-4);
		tree.root.left.right = new TreeNode(3);
		tree.root.left.right.left = new TreeNode(10);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.right.right.right = new TreeNode(1);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(7);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(5);
		/*
		    -4
		      \
		       3
		        \
		         8
		          \
		           1
		 [-4, 3, 8, 1]       
		 Result : 3
		 Because  exist 3 edge
		                
		*/
		tree.straightPath();
	}
}

input

 Longest straight path : 3
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program
    Print nodes at k distance from root
*/
// Binary Tree node
class TreeNode
{
	public: int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		// Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinaryTree
{
	public: TreeNode *root;
	int result;
	BinaryTree()
	{
		this->root = NULL;
		this->result = 0;
	}
	// Find the length of longest straight path in binary tree
	void longestStraightPath(TreeNode *node, TreeNode *parent, int direction)
	{
		if (node == NULL)
		{
			return;
		}
		if (parent == NULL)
		{
			// First node of tree
			// Here 1 indicate if next node exist then straight path will be 1
			this->longestStraightPath(node->left, node, 1);
			this->longestStraightPath(node->right, node, 1);
		}
		else
		{
			if (direction > this->result)
			{
				// Get new result
				this->result = direction;
			}
			if (parent->left == node)
			{
				// Current node exists in left side of parent
				this->longestStraightPath(node->left, node, direction + 1);
				this->longestStraightPath(node->right, node, 1);
			}
			else
			{
				// Current node exists in right side of parent
				this->longestStraightPath(node->left, node, 1);
				this->longestStraightPath(node->right, node, direction + 1);
			}
		}
	}
	// Handles the request of finding longest straight path in tree
	void straightPath()
	{
		this->result = 0;
		this->longestStraightPath(this->root, NULL, 0);
		// Display the calculated result
		cout << "\n Longest straight path : " << this->result;
	}
};
int main()
{
	// Create new binary tree
	BinaryTree *tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	     -4     7    
	     / \     \               
	    2   3     12
	       / \    / 
	      10  8  5
	      /    \  \
	     9      1   12 
	-----------------
	Constructing binary tree
	                
	        
	*/
	tree->root = new TreeNode(4);
	tree->root->left = new TreeNode(-4);
	tree->root->left->right = new TreeNode(3);
	tree->root->left->right->left = new TreeNode(10);
	tree->root->left->right->left->left = new TreeNode(9);
	tree->root->left->right->right = new TreeNode(8);
	tree->root->left->right->right->right = new TreeNode(1);
	tree->root->left->left = new TreeNode(2);
	tree->root->right = new TreeNode(7);
	tree->root->right->right = new TreeNode(12);
	tree->root->right->right->left = new TreeNode(5);
	tree->root->right->right->left->right = new TreeNode(5);
	/*
	    -4
	      \
	       3
	        \
	         8
	          \
	           1
	 [-4, 3, 8, 1]       
	 Result : 3
	 Because  exist 3 edge
	                
	*/
	tree->straightPath();
	return 0;
}

input

 Longest straight path : 3
// Include namespace system
using System;
/*
    Csharp Program
    Print nodes at k distance from root
*/
// Binary Tree node
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public int result;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
		this.result = 0;
	}
	// Find the length of longest straight path in binary tree
	public void longestStraightPath(TreeNode node, 
                                     TreeNode parent, int direction)
	{
		if (node == null)
		{
			return;
		}
		if (parent == null)
		{
			// First node of tree
			// Here 1 indicate if next node exist then straight path will be 1
			this.longestStraightPath(node.left, node, 1);
			this.longestStraightPath(node.right, node, 1);
		}
		else
		{
			if (direction > this.result)
			{
				// Get new result
				this.result = direction;
			}
			if (parent.left == node)
			{
				// Current node exists in left side of parent
				this.longestStraightPath(node.left, node, direction + 1);
				this.longestStraightPath(node.right, node, 1);
			}
			else
			{
				// Current node exists in right side of parent
				this.longestStraightPath(node.left, node, 1);
				this.longestStraightPath(node.right, node, direction + 1);
			}
		}
	}
	// Handles the request of finding longest straight path in tree
	public void straightPath()
	{
		this.result = 0;
		this.longestStraightPath(this.root, null, 0);
		// Display the calculated result
		Console.Write("\n Longest straight path : " + this.result);
	}
	public static void Main(String[] args)
	{
		// Create new binary tree
		BinaryTree tree = new BinaryTree();
		/*
		         4                            
		       /   \    
		     -4     7    
		     / \     \               
		    2   3     12
		       / \    / 
		      10  8  5
		      /    \  \
		     9      1   12 
		-----------------
		Constructing binary tree
		                
		        
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(-4);
		tree.root.left.right = new TreeNode(3);
		tree.root.left.right.left = new TreeNode(10);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.right.right.right = new TreeNode(1);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(7);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(5);
		/*
		    -4
		      \
		       3
		        \
		         8
		          \
		           1
		 [-4, 3, 8, 1]       
		 Result : 3
		 Because  exist 3 edge
		                
		*/
		tree.straightPath();
	}
}

input

 Longest straight path : 3
<?php
/*
    Php Program
    Print nodes at k distance from root
*/
// 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	function __construct()
	{
		$this->root = NULL;
		$this->result = 0;
	}
	// Find the length of longest straight path in binary tree
	public	function longestStraightPath($node, $parent, $direction)
	{
		if ($node == NULL)
		{
			return;
		}
		if ($parent == NULL)
		{
			// First node of tree
			// Here 1 indicate if next node exist then straight path will be 1
			$this->longestStraightPath($node->left, $node, 1);
			$this->longestStraightPath($node->right, $node, 1);
		}
		else
		{
			if ($direction > $this->result)
			{
				// Get new result
				$this->result = $direction;
			}
			if ($parent->left == $node)
			{
				// Current node exists in left side of parent
				$this->longestStraightPath($node->left, $node, $direction + 1);
				$this->longestStraightPath($node->right, $node, 1);
			}
			else
			{
				// Current node exists in right side of parent
				$this->longestStraightPath($node->left, $node, 1);
				$this->longestStraightPath($node->right, $node, $direction + 1);
			}
		}
	}
	// Handles the request of finding longest straight path in tree
	public	function straightPath()
	{
		$this->result = 0;
		$this->longestStraightPath($this->root, NULL, 0);
		// Display the calculated result
		echo("\n Longest straight path : ".$this->result);
	}
}

function main()
{
	// Create new binary tree
	$tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	     -4     7    
	     / \     \               
	    2   3     12
	       / \    / 
	      10  8  5
	      /    \  \
	     9      1   12 
	-----------------
	Constructing binary tree
	                
	        
	*/
	$tree->root = new TreeNode(4);
	$tree->root->left = new TreeNode(-4);
	$tree->root->left->right = new TreeNode(3);
	$tree->root->left->right->left = new TreeNode(10);
	$tree->root->left->right->left->left = new TreeNode(9);
	$tree->root->left->right->right = new TreeNode(8);
	$tree->root->left->right->right->right = new TreeNode(1);
	$tree->root->left->left = new TreeNode(2);
	$tree->root->right = new TreeNode(7);
	$tree->root->right->right = new TreeNode(12);
	$tree->root->right->right->left = new TreeNode(5);
	$tree->root->right->right->left->right = new TreeNode(5);
	/*
	    -4
	      \
	       3
	        \
	         8
	          \
	           1
	 [-4, 3, 8, 1]       
	 Result : 3
	 Because  exist 3 edge
	                
	*/
	$tree->straightPath();
}
main();

input

 Longest straight path : 3
/*
    Node JS Program
    Print nodes at k distance from root
*/
// 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 = 0;
	}
	// Find the length of longest straight path in binary tree
	longestStraightPath(node, parent, direction)
	{
		if (node == null)
		{
			return;
		}
		if (parent == null)
		{
			// First node of tree
			// Here 1 indicate if next node exist then straight path will be 1
			this.longestStraightPath(node.left, node, 1);
			this.longestStraightPath(node.right, node, 1);
		}
		else
		{
			if (direction > this.result)
			{
				// Get new result
				this.result = direction;
			}
			if (parent.left == node)
			{
				// Current node exists in left side of parent
				this.longestStraightPath(node.left, node, direction + 1);
				this.longestStraightPath(node.right, node, 1);
			}
			else
			{
				// Current node exists in right side of parent
				this.longestStraightPath(node.left, node, 1);
				this.longestStraightPath(node.right, node, direction + 1);
			}
		}
	}
	// Handles the request of finding longest straight path in tree
	straightPath()
	{
		this.result = 0;
		this.longestStraightPath(this.root, null, 0);
		// Display the calculated result
		process.stdout.write("\n Longest straight path : " + this.result);
	}
}

function main()
{
	// Create new binary tree
	var tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	     -4     7    
	     / \     \               
	    2   3     12
	       / \    / 
	      10  8  5
	      /    \  \
	     9      1   12 
	-----------------
	Constructing binary tree
	                
	        
	*/
	tree.root = new TreeNode(4);
	tree.root.left = new TreeNode(-4);
	tree.root.left.right = new TreeNode(3);
	tree.root.left.right.left = new TreeNode(10);
	tree.root.left.right.left.left = new TreeNode(9);
	tree.root.left.right.right = new TreeNode(8);
	tree.root.left.right.right.right = new TreeNode(1);
	tree.root.left.left = new TreeNode(2);
	tree.root.right = new TreeNode(7);
	tree.root.right.right = new TreeNode(12);
	tree.root.right.right.left = new TreeNode(5);
	tree.root.right.right.left.right = new TreeNode(5);
	/*
	    -4
	      \
	       3
	        \
	         8
	          \
	           1
	 [-4, 3, 8, 1]       
	 Result : 3
	 Because  exist 3 edge
	                
	*/
	tree.straightPath();
}
main();

input

 Longest straight path : 3
#    Python 3 Program
#    Print nodes at k distance from root

#  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 = 0
	
	#  Find the length of longest straight path in binary tree
	def longestStraightPath(self, node, parent, direction) :
		if (node == None) :
			return
		
		if (parent == None) :
			#  First node of tree
			#  Here 1 indicate if next node exist then straight path will be 1
			self.longestStraightPath(node.left, node, 1)
			self.longestStraightPath(node.right, node, 1)
		else :
			if (direction > self.result) :
				#  Get new result
				self.result = direction
			
			if (parent.left == node) :
				#  Current node exists in left side of parent
				self.longestStraightPath(node.left, node, direction + 1)
				self.longestStraightPath(node.right, node, 1)
			else :
				#  Current node exists in right side of parent
				self.longestStraightPath(node.left, node, 1)
				self.longestStraightPath(node.right, node, direction + 1)
			
		
	
	#  Handles the request of finding longest straight path in tree
	def straightPath(self) :
		self.result = 0
		self.longestStraightPath(self.root, None, 0)
		#  Display the calculated result
		print("\n Longest straight path : ", self.result, end = "")
	

def main() :
	#  Create new binary tree
	tree = BinaryTree()
	#         4                            
	#       /   \    
	#     -4     7    
	#     / \     \               
	#    2   3     12
	#       / \    / 
	#      10  8  5
	#      /    \  \
	#     9      1   12 
	# -----------------
	# Constructing binary tree
	tree.root = TreeNode(4)
	tree.root.left = TreeNode(-4)
	tree.root.left.right = TreeNode(3)
	tree.root.left.right.left = TreeNode(10)
	tree.root.left.right.left.left = TreeNode(9)
	tree.root.left.right.right = TreeNode(8)
	tree.root.left.right.right.right = TreeNode(1)
	tree.root.left.left = TreeNode(2)
	tree.root.right = TreeNode(7)
	tree.root.right.right = TreeNode(12)
	tree.root.right.right.left = TreeNode(5)
	tree.root.right.right.left.right = TreeNode(5)
	#    -4
	#      \
	#       3
	#        \
	#         8
	#          \
	#           1
	# [-4, 3, 8, 1]       
	# Result : 3
	# Because  exist 3 edge
	tree.straightPath()

if __name__ == "__main__": main()

input

 Longest straight path :  3
#    Ruby Program
#    Print nodes at k distance from root

#  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
	attr_accessor :root, :result
	def initialize() 
		self.root = nil
		self.result = 0
	end

	#  Find the length of longest straight path in binary tree
	def longestStraightPath(node, parent, direction) 
		if (node == nil) 
			return
		end

		if (parent == nil) 
			#  First node of tree
			#  Here 1 indicate if next node exist then straight path will be 1
			self.longestStraightPath(node.left, node, 1)
			self.longestStraightPath(node.right, node, 1)
		else 
			if (direction > self.result) 
				#  Get new result
				self.result = direction
			end

			if (parent.left == node) 
				#  Current node exists in left side of parent
				self.longestStraightPath(node.left, node, direction + 1)
				self.longestStraightPath(node.right, node, 1)
			else 
				#  Current node exists in right side of parent
				self.longestStraightPath(node.left, node, 1)
				self.longestStraightPath(node.right, node, direction + 1)
			end

		end

	end

	#  Handles the request of finding longest straight path in tree
	def straightPath() 
		self.result = 0
		self.longestStraightPath(self.root, nil, 0)
		#  Display the calculated result
		print("\n Longest straight path : ", self.result)
	end

end

def main() 
	#  Create new binary tree
	tree = BinaryTree.new()
	#         4                            
	#       /   \    
	#     -4     7    
	#     / \     \               
	#    2   3     12
	#       / \    / 
	#      10  8  5
	#      /    \  \
	#     9      1   12 
	# -----------------
	# Constructing binary tree
	tree.root = TreeNode.new(4)
	tree.root.left = TreeNode.new(-4)
	tree.root.left.right = TreeNode.new(3)
	tree.root.left.right.left = TreeNode.new(10)
	tree.root.left.right.left.left = TreeNode.new(9)
	tree.root.left.right.right = TreeNode.new(8)
	tree.root.left.right.right.right = TreeNode.new(1)
	tree.root.left.left = TreeNode.new(2)
	tree.root.right = TreeNode.new(7)
	tree.root.right.right = TreeNode.new(12)
	tree.root.right.right.left = TreeNode.new(5)
	tree.root.right.right.left.right = TreeNode.new(5)
	#    -4
	#      \
	#       3
	#        \
	#         8
	#          \
	#           1
	# [-4, 3, 8, 1]       
	# Result : 3
	# Because  exist 3 edge
	tree.straightPath()
end

main()

input

 Longest straight path : 3
/*
    Scala Program
    Print nodes at k distance from root
*/
// 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: Int)
{
	def this()
	{
		this(null, 0);
	}
	// Find the length of longest straight path in binary tree
	def longestStraightPath(node: TreeNode, 
                            parent: TreeNode, direction: Int): Unit = {
		if (node == null)
		{
			return;
		}
		if (parent == null)
		{
			// First node of tree
			// Here 1 indicate if next node exist then straight path will be 1
			longestStraightPath(node.left, node, 1);
			longestStraightPath(node.right, node, 1);
		}
		else
		{
			if (direction > this.result)
			{
				// Get new result
				this.result = direction;
			}
			if (parent.left == node)
			{
				// Current node exists in left side of parent
				longestStraightPath(node.left, node, direction + 1);
				longestStraightPath(node.right, node, 1);
			}
			else
			{
				// Current node exists in right side of parent
				longestStraightPath(node.left, node, 1);
				longestStraightPath(node.right, node, direction + 1);
			}
		}
	}
	// Handles the request of finding longest straight path in tree
	def straightPath(): Unit = {
		this.result = 0;
		longestStraightPath(this.root, null, 0);
		// Display the calculated result
		print("\n Longest straight path : " + this.result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create new binary tree
		var tree: BinaryTree = new BinaryTree();
		/*
		         4                            
		       /   \    
		     -4     7    
		     / \     \               
		    2   3     12
		       / \    / 
		      10  8  5
		      /    \  \
		     9      1   12 
		-----------------
		Constructing binary tree
		                
		        
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(-4);
		tree.root.left.right = new TreeNode(3);
		tree.root.left.right.left = new TreeNode(10);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.right.right.right = new TreeNode(1);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(7);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(5);
		/*
		    -4
		      \
		       3
		        \
		         8
		          \
		           1
		 [-4, 3, 8, 1]       
		 Result : 3
		 Because  exist 3 edge
		                
		*/
		tree.straightPath();
	}
}

input

 Longest straight path : 3
/*
    Swift 4 Program
    Print nodes at k distance from root
*/
// 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: Int;
	init()
	{
		self.root = nil;
		self.result = 0;
	}
	// Find the length of longest straight path in binary tree
	func longestStraightPath(_ node: TreeNode? ,
                             _ parent : TreeNode? , _ direction : Int)
	{
		if (node == nil)
		{
			return;
		}
		if (parent == nil)
		{
			// First node of tree
			// Here 1 indicate if next node exist then straight path will be 1
			self.longestStraightPath(node!.left, node, 1);
			self.longestStraightPath(node!.right, node, 1);
		}
		else
		{
			if (direction > self.result)
			{
				// Get new result
				self.result = direction;
			}
			if (parent!.left === node)
			{
				// Current node exists in left side of parent
				self.longestStraightPath(node!.left, node, direction + 1);
				self.longestStraightPath(node!.right, node, 1);
			}
			else
			{
				// Current node exists in right side of parent
				self.longestStraightPath(node!.left, node, 1);
				self.longestStraightPath(node!.right, node, direction + 1);
			}
		}
	}
	// Handles the request of finding longest straight path in tree
	func straightPath()
	{
		self.result = 0;
		self.longestStraightPath(self.root, nil, 0);
		// Display the calculated result
		print("\n Longest straight path : ", self.result, terminator: "");
	}
}
func main()
{
	// Create new binary tree
	let tree: BinaryTree = BinaryTree();
	/*
	         4                            
	       /   \    
	     -4     7    
	     / \     \               
	    2   3     12
	       / \    / 
	      10  8  5
	      /    \  \
	     9      1   12 
	-----------------
	Constructing binary tree
	                
	        
	*/
	tree.root = TreeNode(4);
	tree.root!.left = TreeNode(-4);
	tree.root!.left!.right = TreeNode(3);
	tree.root!.left!.right!.left = TreeNode(10);
	tree.root!.left!.right!.left!.left = TreeNode(9);
	tree.root!.left!.right!.right = TreeNode(8);
	tree.root!.left!.right!.right!.right = TreeNode(1);
	tree.root!.left!.left = TreeNode(2);
	tree.root!.right = TreeNode(7);
	tree.root!.right!.right = TreeNode(12);
	tree.root!.right!.right!.left = TreeNode(5);
	tree.root!.right!.right!.left!.right = TreeNode(5);
	/*
	    -4
	      \
	       3
	        \
	         8
	          \
	           1
	 [-4, 3, 8, 1]       
	 Result : 3
	 Because  exist 3 edge
	                
	*/
	tree.straightPath();
}
main();

input

 Longest straight path :  3
/*
    Kotlin Program
    Print nodes at k distance from root
*/
// 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: Int;
	constructor()
	{
		this.root = null;
		this.result = 0;
	}
	// Find the length of longest straight path in binary tree
	fun longestStraightPath(node: TreeNode ? , 
                            parent : TreeNode ? , direction : Int): Unit
	{
		if (node == null)
		{
			return;
		}
		if (parent == null)
		{
			// First node of tree
			// Here 1 indicate if next node exist then straight path will be 1
			this.longestStraightPath(node.left, node, 1);
			this.longestStraightPath(node.right, node, 1);
		}
		else
		{
			if (direction > this.result)
			{
				// Get new result
				this.result = direction;
			}
			if (parent.left == node)
			{
				// Current node exists in left side of parent
				this.longestStraightPath(node.left, node, direction + 1);
				this.longestStraightPath(node.right, node, 1);
			}
			else
			{
				// Current node exists in right side of parent
				this.longestStraightPath(node.left, node, 1);
				this.longestStraightPath(node.right, node, direction + 1);
			}
		}
	}
	// Handles the request of finding longest straight path in tree
	fun straightPath(): Unit
	{
		this.result = 0;
		this.longestStraightPath(this.root, null, 0);
		// Display the calculated result
		print("\n Longest straight path : " + this.result);
	}
}
fun main(args: Array < String > ): Unit
{
	// Create new binary tree
	val tree: BinaryTree = BinaryTree();
	/*
	         4                            
	       /   \    
	     -4     7    
	     / \     \               
	    2   3     12
	       / \    / 
	      10  8  5
	      /    \  \
	     9      1   12 
	-----------------
	Constructing binary tree
	                
	        
	*/
	tree.root = TreeNode(4);
	tree.root?.left = TreeNode(-4);
	tree.root?.left?.right = TreeNode(3);
	tree.root?.left?.right?.left = TreeNode(10);
	tree.root?.left?.right?.left?.left = TreeNode(9);
	tree.root?.left?.right?.right = TreeNode(8);
	tree.root?.left?.right?.right?.right = TreeNode(1);
	tree.root?.left?.left = TreeNode(2);
	tree.root?.right = TreeNode(7);
	tree.root?.right?.right = TreeNode(12);
	tree.root?.right?.right?.left = TreeNode(5);
	tree.root?.right?.right?.left?.right = TreeNode(5);
	/*
	    -4
	      \
	       3
	        \
	         8
	          \
	           1
	 [-4, 3, 8, 1]       
	 Result : 3
	 Because  exist 3 edge
	                
	*/
	tree.straightPath();
}

input

 Longest straight path : 3

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