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
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