Posted on by Kalkicode
Code Binary Tree

Print cousins of a given node in binary tree in typescript

Ts program for Print cousins of a given node in binary tree. Here problem description and other solutions.

/* 
  TypeScript Program 
  Print cousins of given node in a binary tree
*/
// Node of Binary Tree
class TreeNode
{
	public data: number;
	public left: TreeNode;
	public right: TreeNode;
	constructor(data: number)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	public root: TreeNode;
	public height: number;
	constructor()
	{
		// Set initial tree root to null
		this.root = null;
		this.height = 0;
	}
	// Display Inorder view of binary tree
	public inorder(node: TreeNode)
	{
		if (node != null)
		{
			// Executing left subtree
			this.inorder(node.left);
			// Print node value
			console.log("  " + node.data);
			// Executing right subtree
			this.inorder(node.right);
		}
	}
	// Check whether given key node are exist in binary tree or not.
	// If key exists then return its parent node and
	// calculate the height of key node
	public TreeNode nodeHeight(node: TreeNode, level: number, key: number)
	{
		if (node == null)
		{
			// When get empty node
			return null;
		}
		else if ((node.left != null && node.left.data == key) || 
                 (node.right != null && node.right.data == key))
		{
			// When given key exists in binary tree
			// Get node height
			this.height = level + 1;
			// return parent node
			return node;
		}
		else
		{
			// Used to detect key node in left subtree
			var result = this.nodeHeight(node.left, level + 1, key);
			if (result == null)
			{
				// Used to detect key node in right subtree
				result = this.nodeHeight(node.right, level + 1, key);
			}
			return result;
		}
	}
	// Print cousin nodes in given level
	public findCousinNode(node: TreeNode, 
                          depth: number, 
                          parent: TreeNode, 
                          level: number)
	{
		if (node == null || parent == node || level > depth)
		{
			// When node is null
			// or when root node is parent of key
			// or when level exceed print level
			return;
		}
		if (depth == level)
		{
			// Display cousin nodes
			console.log(" " + node.data);
			return;
		}
		// Recursively execute left and right subtree
		this.findCousinNode(node.left, depth, parent, level + 1);
		this.findCousinNode(node.right, depth, parent, level + 1);
	}
	// This are handling the request of
	// printing cousin node of given key
	public printCousins(key: number)
	{
		if (this.root.data == key)
		{
			// There are no cousins of root node
			console.log("Cousin nodes of " + key + " is : None ");
			return;
		}
		this.height = 0;
		// First get height and parent node of given key
		var parent = this.nodeHeight(this.root, 0, key);
		if (parent != null)
		{
			console.log("Cousin nodes of " + key + " is : ");
			this.findCousinNode(this.root, this.height, parent, 0);
			console.log("\n");
		}
		else
		{
			console.log("Given key node [" + key + "] is not exist");
		}
	}
	public static main(args: string[])
	{
		// Make object of Binary Tree
		var tree = new BinaryTree();
		/*
		  Construct Binary Tree 
		  -----------------------
		         1
		       /   \
		      6     8
		     / \   / \
		    2   3 7   5
		   /           \
		  9             11
		*/
		// Add nodes
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(6);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(8);
		tree.root.right.right = new TreeNode(5);
		tree.root.right.left = new TreeNode(7);
		tree.root.left.right = new TreeNode(3);
		tree.root.left.left.left = new TreeNode(9);
		tree.root.right.right.right = new TreeNode(11);
		// Display tree elements
		console.log("\nBinary Tree Nodes : ");
		tree.inorder(tree.root);
		console.log("\n");
		// Test Cases
		tree.printCousins(2);
		tree.printCousins(1);
		tree.printCousins(5);
		tree.printCousins(4);
		tree.printCousins(9);
	}
}
BinaryTree.main([]);
/*
 file : code.ts
 tsc --target es6 code.ts
 node code.js
 */

Output

Binary Tree Nodes :
  9
  2
  6
  3
  1
  7
  8
  5
  11


Cousin nodes of 2 is :
 7
 5


Cousin nodes of 1 is : None
Cousin nodes of 5 is :
 2
 3


Given key node [4] is not exist
Cousin nodes of 9 is :
 11

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