Check whether binary tree contains only one path
When there is only one path from the root of a tree to a leaf, it is called a single path or one path tree. In other words, there should be no more than one child node in a tree node. For example.
Our goal is to detect or check tree contains single path or not. Here given code implementation process.
/*
C Program
Check whether binary tree contains only one path
*/
#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;
}
// returns a new node of tree
struct TreeNode *newTreeNode(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;
}
int checkOnePath(struct TreeNode *node)
{
if (node == NULL)
{
return 1;
}
if (node->left != NULL && node->right != NULL)
{
// More than one path possible
return 0;
}
return checkOnePath(node->left) && checkOnePath(node->right);
}
void isOnePath(struct BinaryTree *tree)
{
if (tree->root == NULL)
{
// Tree empty
printf("\n No");
}
else
{
if (checkOnePath(tree->root) == 1)
{
printf("\n Yes");
}
else
{
printf("\n No");
}
}
}
int main()
{
struct BinaryTree *tree1 = newTree();
struct BinaryTree *tree2 = newTree();
struct BinaryTree *tree3 = newTree();
/*
Tree 1
--------
5
/
1
\
7
\
6
/
2
*/
tree1->root = newTreeNode(5);
tree1->root->left = newTreeNode(1);
tree1->root->left->right = newTreeNode(7);
tree1->root->left->right->right = newTreeNode(6);
tree1->root->left->right->right->left = newTreeNode(2);
/*
Tree 2
-----------
15
/
8
\
7
/ \
3 6
/
2
*/
tree2->root = newTreeNode(15);
tree2->root->left = newTreeNode(8);
tree2->root->left->right = newTreeNode(7);
tree2->root->left->right->left = newTreeNode(3);
tree2->root->left->right->right = newTreeNode(6);
tree2->root->left->right->right->left = newTreeNode(2);
/*
Tree 3
-----------
15
\
8
/
7
/
3
\
1
*/
tree3->root = newTreeNode(15);
tree3->root->right = newTreeNode(8);
tree3->root->right->left = newTreeNode(7);
tree3->root->right->left->left = newTreeNode(3);
tree3->root->right->left->left->right = newTreeNode(1);
// Test
isOnePath(tree1);
isOnePath(tree2);
isOnePath(tree3);
return 0;
}Output
Yes
No
Yes// Java program for
// Check whether binary tree contains only one path
class TreeNode
{
// Data value
public int data;
// Indicates left and right subtree
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
public boolean checkOnePath(TreeNode node)
{
if (node == null)
{
return true;
}
if (node.left != null && node.right != null)
{
// More than one path possible
return false;
}
return checkOnePath(node.left) && checkOnePath(node.right);
}
public void isOnePath()
{
if (this.root == null)
{
// Tree empty
System.out.print("\n No");
}
else
{
if (checkOnePath(this.root))
{
System.out.print("\n Yes");
}
else
{
System.out.print("\n No");
}
}
}
public static void main(String[] args)
{
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
BinaryTree tree3 = new BinaryTree();
/*
Tree 1
--------
5
/
1
\
7
\
6
/
2
*/
tree1.root = new TreeNode(5);
tree1.root.left = new TreeNode(1);
tree1.root.left.right = new TreeNode(7);
tree1.root.left.right.right = new TreeNode(6);
tree1.root.left.right.right.left = new TreeNode(2);
/*
Tree 2
-----------
15
/
8
\
7
/ \
3 6
/
2
*/
tree2.root = new TreeNode(15);
tree2.root.left = new TreeNode(8);
tree2.root.left.right = new TreeNode(7);
tree2.root.left.right.left = new TreeNode(3);
tree2.root.left.right.right = new TreeNode(6);
tree2.root.left.right.right.left = new TreeNode(2);
/*
Tree 3
-----------
15
\
8
/
7
/
3
\
1
*/
tree3.root = new TreeNode(15);
tree3.root.right = new TreeNode(8);
tree3.root.right.left = new TreeNode(7);
tree3.root.right.left.left = new TreeNode(3);
tree3.root.right.left.left.right = new TreeNode(1);
// Test
tree1.isOnePath();
tree2.isOnePath();
tree3.isOnePath();
}
}Output
Yes
No
Yes// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Check whether binary tree contains only one path
class TreeNode
{
public:
// Data value
int data;
// Indicates left and right subtree
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
bool checkOnePath(TreeNode *node)
{
if (node == NULL)
{
return true;
}
if (node->left != NULL && node->right != NULL)
{
// More than one path possible
return false;
}
return this->checkOnePath(node->left) &&
this->checkOnePath(node->right);
}
void isOnePath()
{
if (this->root == NULL)
{
// Tree empty
cout << "\n No";
}
else
{
if (this->checkOnePath(this->root))
{
cout << "\n Yes";
}
else
{
cout << "\n No";
}
}
}
};
int main()
{
BinaryTree *tree1 = new BinaryTree();
BinaryTree *tree2 = new BinaryTree();
BinaryTree *tree3 = new BinaryTree();
/*
Tree 1
--------
5
/
1
\
7
\
6
/
2
*/
tree1->root = new TreeNode(5);
tree1->root->left = new TreeNode(1);
tree1->root->left->right = new TreeNode(7);
tree1->root->left->right->right = new TreeNode(6);
tree1->root->left->right->right->left = new TreeNode(2);
/*
Tree 2
-----------
15
/
8
\
7
/ \
3 6
/
2
*/
tree2->root = new TreeNode(15);
tree2->root->left = new TreeNode(8);
tree2->root->left->right = new TreeNode(7);
tree2->root->left->right->left = new TreeNode(3);
tree2->root->left->right->right = new TreeNode(6);
tree2->root->left->right->right->left = new TreeNode(2);
/*
Tree 3
--------
15
\
8
/
7
/
3
\
1
*/
tree3->root = new TreeNode(15);
tree3->root->right = new TreeNode(8);
tree3->root->right->left = new TreeNode(7);
tree3->root->right->left->left = new TreeNode(3);
tree3->root->right->left->left->right = new TreeNode(1);
// Test
tree1->isOnePath();
tree2->isOnePath();
tree3->isOnePath();
return 0;
}Output
Yes
No
Yespackage main
import "fmt"
// Go program for
// Check whether binary tree contains only one path
type TreeNode struct {
// Data value
data int
// Indicates left and right subtree
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
me.data = data
me.left = nil
me.right = nil
return me
}
type BinaryTree struct {
root * TreeNode
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
me.root = nil
return me
}
func(this BinaryTree) checkOnePath(node * TreeNode) bool {
if node == nil {
return true
}
if node.left != nil && node.right != nil {
// More than one path possible
return false
}
return this.checkOnePath(node.left) && this.checkOnePath(node.right)
}
func(this BinaryTree) isOnePath() {
if this.root == nil {
// Tree empty
fmt.Print("\n No")
} else {
if this.checkOnePath(this.root) {
fmt.Print("\n Yes")
} else {
fmt.Print("\n No")
}
}
}
func main() {
var tree1 * BinaryTree = getBinaryTree()
var tree2 * BinaryTree = getBinaryTree()
var tree3 * BinaryTree = getBinaryTree()
/*
Tree 1
--------
5
/
1
\
7
\
6
/
2
*/
tree1.root = getTreeNode(5)
tree1.root.left = getTreeNode(1)
tree1.root.left.right = getTreeNode(7)
tree1.root.left.right.right = getTreeNode(6)
tree1.root.left.right.right.left = getTreeNode(2)
/*
Tree 2
-----------
15
/
8
\
7
/ \
3 6
/
2
*/
tree2.root = getTreeNode(15)
tree2.root.left = getTreeNode(8)
tree2.root.left.right = getTreeNode(7)
tree2.root.left.right.left = getTreeNode(3)
tree2.root.left.right.right = getTreeNode(6)
tree2.root.left.right.right.left = getTreeNode(2)
/*
Tree 3
--------
15
\
8
/
7
/
3
\
1
*/
tree3.root = getTreeNode(15)
tree3.root.right = getTreeNode(8)
tree3.root.right.left = getTreeNode(7)
tree3.root.right.left.left = getTreeNode(3)
tree3.root.right.left.left.right = getTreeNode(1)
// Test
tree1.isOnePath()
tree2.isOnePath()
tree3.isOnePath()
}Output
Yes
No
Yes// Include namespace system
using System;
// Csharp program for
// Check whether binary tree contains only one path
public class TreeNode
{
// Data value
public int data;
// Indicates left and right subtree
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
public Boolean checkOnePath(TreeNode node)
{
if (node == null)
{
return true;
}
if (node.left != null && node.right != null)
{
// More than one path possible
return false;
}
return this.checkOnePath(node.left) &&
this.checkOnePath(node.right);
}
public void isOnePath()
{
if (this.root == null)
{
// Tree empty
Console.Write("\n No");
}
else
{
if (this.checkOnePath(this.root))
{
Console.Write("\n Yes");
}
else
{
Console.Write("\n No");
}
}
}
public static void Main(String[] args)
{
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
BinaryTree tree3 = new BinaryTree();
/*
Tree 1
--------
5
/
1
\
7
\
6
/
2
*/
tree1.root = new TreeNode(5);
tree1.root.left = new TreeNode(1);
tree1.root.left.right = new TreeNode(7);
tree1.root.left.right.right = new TreeNode(6);
tree1.root.left.right.right.left = new TreeNode(2);
/*
Tree 2
-----------
15
/
8
\
7
/ \
3 6
/
2
*/
tree2.root = new TreeNode(15);
tree2.root.left = new TreeNode(8);
tree2.root.left.right = new TreeNode(7);
tree2.root.left.right.left = new TreeNode(3);
tree2.root.left.right.right = new TreeNode(6);
tree2.root.left.right.right.left = new TreeNode(2);
/*
Tree 3
--------
15
\
8
/
7
/
3
\
1
*/
tree3.root = new TreeNode(15);
tree3.root.right = new TreeNode(8);
tree3.root.right.left = new TreeNode(7);
tree3.root.right.left.left = new TreeNode(3);
tree3.root.right.left.left.right = new TreeNode(1);
// Test
tree1.isOnePath();
tree2.isOnePath();
tree3.isOnePath();
}
}Output
Yes
No
Yes<?php
// Php program for
// Check whether binary tree contains only one path
class TreeNode
{
// Data value
public $data;
// Indicates left and right subtree
public $left;
public $right;
public function __construct($data)
{
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
class BinaryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
public function checkOnePath($node)
{
if ($node == NULL)
{
return true;
}
if ($node->left != NULL && $node->right != NULL)
{
// More than one path possible
return false;
}
return $this->checkOnePath($node->left) &&
$this->checkOnePath($node->right);
}
public function isOnePath()
{
if ($this->root == NULL)
{
// Tree empty
echo("\n No");
}
else
{
if ($this->checkOnePath($this->root))
{
echo("\n Yes");
}
else
{
echo("\n No");
}
}
}
}
function main()
{
$tree1 = new BinaryTree();
$tree2 = new BinaryTree();
$tree3 = new BinaryTree();
/*
Tree 1
--------
5
/
1
\
7
\
6
/
2
*/
$tree1->root = new TreeNode(5);
$tree1->root->left = new TreeNode(1);
$tree1->root->left->right = new TreeNode(7);
$tree1->root->left->right->right = new TreeNode(6);
$tree1->root->left->right->right->left = new TreeNode(2);
/*
Tree 2
-----------
15
/
8
\
7
/ \
3 6
/
2
*/
$tree2->root = new TreeNode(15);
$tree2->root->left = new TreeNode(8);
$tree2->root->left->right = new TreeNode(7);
$tree2->root->left->right->left = new TreeNode(3);
$tree2->root->left->right->right = new TreeNode(6);
$tree2->root->left->right->right->left = new TreeNode(2);
/*
Tree 3
--------
15
\
8
/
7
/
3
\
1
*/
$tree3->root = new TreeNode(15);
$tree3->root->right = new TreeNode(8);
$tree3->root->right->left = new TreeNode(7);
$tree3->root->right->left->left = new TreeNode(3);
$tree3->root->right->left->left->right = new TreeNode(1);
// Test
$tree1->isOnePath();
$tree2->isOnePath();
$tree3->isOnePath();
}
main();Output
Yes
No
Yes// Node JS program for
// Check whether binary tree contains only one path
class TreeNode
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
checkOnePath(node)
{
if (node == null)
{
return true;
}
if (node.left != null && node.right != null)
{
// More than one path possible
return false;
}
return this.checkOnePath(node.left) &&
this.checkOnePath(node.right);
}
isOnePath()
{
if (this.root == null)
{
// Tree empty
process.stdout.write("\n No");
}
else
{
if (this.checkOnePath(this.root))
{
process.stdout.write("\n Yes");
}
else
{
process.stdout.write("\n No");
}
}
}
}
function main()
{
var tree1 = new BinaryTree();
var tree2 = new BinaryTree();
var tree3 = new BinaryTree();
/*
Tree 1
--------
5
/
1
\
7
\
6
/
2
*/
tree1.root = new TreeNode(5);
tree1.root.left = new TreeNode(1);
tree1.root.left.right = new TreeNode(7);
tree1.root.left.right.right = new TreeNode(6);
tree1.root.left.right.right.left = new TreeNode(2);
/*
Tree 2
-----------
15
/
8
\
7
/ \
3 6
/
2
*/
tree2.root = new TreeNode(15);
tree2.root.left = new TreeNode(8);
tree2.root.left.right = new TreeNode(7);
tree2.root.left.right.left = new TreeNode(3);
tree2.root.left.right.right = new TreeNode(6);
tree2.root.left.right.right.left = new TreeNode(2);
/*
Tree 3
--------
15
\
8
/
7
/
3
\
1
*/
tree3.root = new TreeNode(15);
tree3.root.right = new TreeNode(8);
tree3.root.right.left = new TreeNode(7);
tree3.root.right.left.left = new TreeNode(3);
tree3.root.right.left.left.right = new TreeNode(1);
// Test
tree1.isOnePath();
tree2.isOnePath();
tree3.isOnePath();
}
main();Output
Yes
No
Yes# Python 3 program for
# Check whether binary tree contains only one path
class TreeNode :
# Data value
# Indicates left and right subtree
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
def checkOnePath(self, node) :
if (node == None) :
return True
if (node.left != None and node.right != None) :
# More than one path possible
return False
return self.checkOnePath(node.left) and self.checkOnePath(node.right)
def isOnePath(self) :
if (self.root == None) :
# Tree empty
print("\n No", end = "")
else :
if (self.checkOnePath(self.root)) :
print("\n Yes", end = "")
else :
print("\n No", end = "")
def main() :
tree1 = BinaryTree()
tree2 = BinaryTree()
tree3 = BinaryTree()
# Tree 1
# --------
# 5
# /
# 1
# \
# 7
# \
# 6
# /
# 2
tree1.root = TreeNode(5)
tree1.root.left = TreeNode(1)
tree1.root.left.right = TreeNode(7)
tree1.root.left.right.right = TreeNode(6)
tree1.root.left.right.right.left = TreeNode(2)
# Tree 2
# -----------
# 15
# /
# 8
# \
# 7
# / \
# 3 6
# /
# 2
tree2.root = TreeNode(15)
tree2.root.left = TreeNode(8)
tree2.root.left.right = TreeNode(7)
tree2.root.left.right.left = TreeNode(3)
tree2.root.left.right.right = TreeNode(6)
tree2.root.left.right.right.left = TreeNode(2)
# Tree 3
# --------
# 15
# \
# 8
# /
# 7
# /
# 3
# \
# 1
tree3.root = TreeNode(15)
tree3.root.right = TreeNode(8)
tree3.root.right.left = TreeNode(7)
tree3.root.right.left.left = TreeNode(3)
tree3.root.right.left.left.right = TreeNode(1)
# Test
tree1.isOnePath()
tree2.isOnePath()
tree3.isOnePath()
if __name__ == "__main__": main()Output
Yes
No
Yes# Ruby program for
# Check whether binary tree contains only one path
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
# Data value
# Indicates left and right subtree
def initialize(data)
self.data = data
self.left = nil
self.right = nil
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
def checkOnePath(node)
if (node == nil)
return true
end
if (node.left != nil && node.right != nil)
# More than one path possible
return false
end
return self.checkOnePath(node.left) && self.checkOnePath(node.right)
end
def isOnePath()
if (self.root == nil)
# Tree empty
print("\n No")
else
if (self.checkOnePath(self.root))
print("\n Yes")
else
print("\n No")
end
end
end
end
def main()
tree1 = BinaryTree.new()
tree2 = BinaryTree.new()
tree3 = BinaryTree.new()
# Tree 1
# --------
# 5
# /
# 1
# \
# 7
# \
# 6
# /
# 2
tree1.root = TreeNode.new(5)
tree1.root.left = TreeNode.new(1)
tree1.root.left.right = TreeNode.new(7)
tree1.root.left.right.right = TreeNode.new(6)
tree1.root.left.right.right.left = TreeNode.new(2)
# Tree 2
# -----------
# 15
# /
# 8
# \
# 7
# / \
# 3 6
# /
# 2
tree2.root = TreeNode.new(15)
tree2.root.left = TreeNode.new(8)
tree2.root.left.right = TreeNode.new(7)
tree2.root.left.right.left = TreeNode.new(3)
tree2.root.left.right.right = TreeNode.new(6)
tree2.root.left.right.right.left = TreeNode.new(2)
# Tree 3
# --------
# 15
# \
# 8
# /
# 7
# /
# 3
# \
# 1
tree3.root = TreeNode.new(15)
tree3.root.right = TreeNode.new(8)
tree3.root.right.left = TreeNode.new(7)
tree3.root.right.left.left = TreeNode.new(3)
tree3.root.right.left.left.right = TreeNode.new(1)
# Test
tree1.isOnePath()
tree2.isOnePath()
tree3.isOnePath()
end
main()Output
Yes
No
Yes// Scala program for
// Check whether binary tree contains only one path
class TreeNode(
// Data value
var data: Int,
// Indicates left and right subtree
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def checkOnePath(node: TreeNode): Boolean = {
if (node == null)
{
return true;
}
if (node.left != null && node.right != null)
{
// More than one path possible
return false;
}
return checkOnePath(node.left) && checkOnePath(node.right);
}
def isOnePath(): Unit = {
if (this.root == null)
{
// Tree empty
print("\n No");
}
else
{
if (checkOnePath(this.root))
{
print("\n Yes");
}
else
{
print("\n No");
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree1: BinaryTree = new BinaryTree();
var tree2: BinaryTree = new BinaryTree();
var tree3: BinaryTree = new BinaryTree();
/*
Tree 1
--------
5
/
1
\
7
\
6
/
2
*/
tree1.root = new TreeNode(5);
tree1.root.left = new TreeNode(1);
tree1.root.left.right = new TreeNode(7);
tree1.root.left.right.right = new TreeNode(6);
tree1.root.left.right.right.left = new TreeNode(2);
/*
Tree 2
-----------
15
/
8
\
7
/ \
3 6
/
2
*/
tree2.root = new TreeNode(15);
tree2.root.left = new TreeNode(8);
tree2.root.left.right = new TreeNode(7);
tree2.root.left.right.left = new TreeNode(3);
tree2.root.left.right.right = new TreeNode(6);
tree2.root.left.right.right.left = new TreeNode(2);
/*
Tree 3
--------
15
\
8
/
7
/
3
\
1
*/
tree3.root = new TreeNode(15);
tree3.root.right = new TreeNode(8);
tree3.root.right.left = new TreeNode(7);
tree3.root.right.left.left = new TreeNode(3);
tree3.root.right.left.left.right = new TreeNode(1);
// Test
tree1.isOnePath();
tree2.isOnePath();
tree3.isOnePath();
}
}Output
Yes
No
Yes// Swift 4 program for
// Check whether binary tree contains only one path
class TreeNode
{
// Data value
var data: Int;
// Indicates left and right subtree
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func checkOnePath(_ node: TreeNode? ) -> Bool
{
if (node == nil)
{
return true;
}
if (node!.left != nil && node!.right != nil)
{
// More than one path possible
return false;
}
return self.checkOnePath(node!.left) &&
self.checkOnePath(node!.right);
}
func isOnePath()
{
if (self.root == nil)
{
// Tree empty
print("\n No", terminator: "");
}
else
{
if (self.checkOnePath(self.root))
{
print("\n Yes", terminator: "");
}
else
{
print("\n No", terminator: "");
}
}
}
}
func main()
{
let tree1: BinaryTree = BinaryTree();
let tree2: BinaryTree = BinaryTree();
let tree3: BinaryTree = BinaryTree();
/*
Tree 1
--------
5
/
1
\
7
\
6
/
2
*/
tree1.root = TreeNode(5);
tree1.root!.left = TreeNode(1);
tree1.root!.left!.right = TreeNode(7);
tree1.root!.left!.right!.right = TreeNode(6);
tree1.root!.left!.right!.right!.left = TreeNode(2);
/*
Tree 2
-----------
15
/
8
\
7
/ \
3 6
/
2
*/
tree2.root = TreeNode(15);
tree2.root!.left = TreeNode(8);
tree2.root!.left!.right = TreeNode(7);
tree2.root!.left!.right!.left = TreeNode(3);
tree2.root!.left!.right!.right = TreeNode(6);
tree2.root!.left!.right!.right!.left = TreeNode(2);
/*
Tree 3
--------
15
\
8
/
7
/
3
\
1
*/
tree3.root = TreeNode(15);
tree3.root!.right = TreeNode(8);
tree3.root!.right!.left = TreeNode(7);
tree3.root!.right!.left!.left = TreeNode(3);
tree3.root!.right!.left!.left!.right = TreeNode(1);
// Test
tree1.isOnePath();
tree2.isOnePath();
tree3.isOnePath();
}
main();Output
Yes
No
Yes// Kotlin program for
// Check whether binary tree contains only one path
class TreeNode
{
// Data value
var data: Int;
// Indicates left and right subtree
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun checkOnePath(node: TreeNode ? ): Boolean
{
if (node == null)
{
return true;
}
if (node.left != null && node.right != null)
{
// More than one path possible
return false;
}
return this.checkOnePath(node.left) &&
this.checkOnePath(node.right);
}
fun isOnePath(): Unit
{
if (this.root == null)
{
// Tree empty
print("\n No");
}
else
{
if (this.checkOnePath(this.root))
{
print("\n Yes");
}
else
{
print("\n No");
}
}
}
}
fun main(args: Array < String > ): Unit
{
val tree1: BinaryTree = BinaryTree();
val tree2: BinaryTree = BinaryTree();
val tree3: BinaryTree = BinaryTree();
/*
Tree 1
--------
5
/
1
\
7
\
6
/
2
*/
tree1.root = TreeNode(5);
tree1.root?.left = TreeNode(1);
tree1.root?.left?.right = TreeNode(7);
tree1.root?.left?.right?.right = TreeNode(6);
tree1.root?.left?.right?.right?.left = TreeNode(2);
/*
Tree 2
-----------
15
/
8
\
7
/ \
3 6
/
2
*/
tree2.root = TreeNode(15);
tree2.root?.left = TreeNode(8);
tree2.root?.left?.right = TreeNode(7);
tree2.root?.left?.right?.left = TreeNode(3);
tree2.root?.left?.right?.right = TreeNode(6);
tree2.root?.left?.right?.right?.left = TreeNode(2);
/*
Tree 3
--------
15
\
8
/
7
/
3
\
1
*/
tree3.root = TreeNode(15);
tree3.root?.right = TreeNode(8);
tree3.root?.right?.left = TreeNode(7);
tree3.root?.right?.left?.left = TreeNode(3);
tree3.root?.right?.left?.left?.right = TreeNode(1);
// Test
tree1.isOnePath();
tree2.isOnePath();
tree3.isOnePath();
}Output
Yes
No
Yes
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