Skip to main content

Check for foldable binary tree in node js

Js program for Check for foldable binary tree. Here problem description and explanation.

/* 
  Node JS program for
  Check if binary tree is foldable binary tree
  Using recursion
*/
// 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;
	}
	isFoldable(leftRoot, rightRoot)
	{
		if (leftRoot == null && rightRoot == null)
		{
			// When both node empty
			return true;
		}
		else if (leftRoot != null && rightRoot != null &&
                 this.isFoldable(leftRoot.left, rightRoot.right) && 
                 this.isFoldable(leftRoot.right, rightRoot.left))
		{
			// When
			// Valid the properties of foldable tree
			return true;
		}
		// Fail case
		return false;
	}
	// Display tree element inorder form
	inorder(node)
	{
		if (node != null)
		{
			// Visit to left subtree
			this.inorder(node.left);
			// Print node value
			process.stdout.write("  " + node.data);
			// Visit to right subtree
			this.inorder(node.right);
		}
	}
}

function main()
{
	// Create new tree
	var tree = new BinaryTree();
	/*
	   Binary Tree
	  -----------------------
	       5
	     /   \
	    7     4
	   /       \
	  1         2
	   \       /
	    2     5
	*/
	// Binary tree nodes
	tree.root = new TreeNode(5);
	tree.root.left = new TreeNode(7);
	tree.root.right = new TreeNode(4);
	tree.root.left.left = new TreeNode(1);
	tree.root.right.right = new TreeNode(2);
	tree.root.right.right.left = new TreeNode(5);
	tree.root.left.left.right = new TreeNode(2);
	// Display Tree elements
	tree.inorder(tree.root);
	var result = tree.isFoldable(tree.root.left, 
                                 tree.root.right);
	if (result == true)
	{
		console.log("\n Foldable Tree");
	}
	else
	{
		console.log("\n Not Foldable Tree");
	}
	/*
	         5
	       /   \
	      7     4
	     /       \
	    1         2
	     \       /
	      2     5
	       \
	        3  
	*/
	// Case 2
	tree.root.left.left.right.right = new TreeNode(3);
	tree.inorder(tree.root);
	result = tree.isFoldable(tree.root.left, 
                             tree.root.right);
	if (result == true)
	{
		console.log("\n Foldable Tree");
	}
	else
	{
		console.log("\n Not Foldable Tree");
	}
}
// Start program execution
main();

Output

  1  2  7  5  4  5  2
 Foldable Tree
  1  2  3  7  5  4  5  2
 Not Foldable Tree




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