Check for foldable binary tree in swift
Swift program for Check for foldable binary tree. Here problem description and other solutions.
import Foundation
/*
Swift 4 program for
Check if binary tree is foldable binary tree
Using recursion
*/
// 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? ;
init()
{
self.root = nil;
}
func isFoldable(_ leftRoot: TreeNode? ,
_ rightRoot : TreeNode? ) -> Bool
{
if (leftRoot == nil && rightRoot == nil)
{
// When both node empty
return true;
}
else if (leftRoot != nil && rightRoot != nil &&
self.isFoldable(leftRoot!.left, rightRoot!.right) &&
self.isFoldable(leftRoot!.right, rightRoot!.left))
{
// When
// Valid the properties of foldable tree
return true;
}
// Fail case
return false;
}
// Display tree element inorder form
func inorder(_ node: TreeNode? )
{
if (node != nil)
{
// Visit to left subtree
self.inorder(node!.left);
// Print node value
print("",node!.data, terminator: " ");
// Visit to right subtree
self.inorder(node!.right);
}
}
static func main()
{
// Create new tree
let tree: BinaryTree = BinaryTree();
/*
Binary Tree
-----------------------
5
/ \
7 4
/ \
1 2
\ /
2 5
*/
// Binary tree nodes
tree.root = TreeNode(5);
tree.root!.left = TreeNode(7);
tree.root!.right = TreeNode(4);
tree.root!.left!.left = TreeNode(1);
tree.root!.right!.right = TreeNode(2);
tree.root!.right!.right!.left = TreeNode(5);
tree.root!.left!.left!.right = TreeNode(2);
// Display Tree elements
tree.inorder(tree.root);
var result: Bool = tree.isFoldable(
tree.root!.left, tree.root!.right);
if (result == true)
{
print("\n Foldable Tree");
}
else
{
print("\n Not Foldable Tree");
}
/*
5
/ \
7 4
/ \
1 2
\ /
2 5
\
3
*/
// Case 2
tree.root!.left!.left!.right!.right = TreeNode(3);
tree.inorder(tree.root);
result = tree.isFoldable(
tree.root!.left, tree.root!.right);
if (result == true)
{
print("\n Foldable Tree");
}
else
{
print("\n Not Foldable Tree");
}
}
}
BinaryTree.main();
Output
1 2 7 5 4 5 2
Foldable Tree
1 2 3 7 5 4 5 2
Not Foldable Tree
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