Skip to main content

lowest common ancestor of a binary search tree in typescript

Find LCA of BST node

Ts program for lowest common ancestor of a binary search tree. Here mentioned other language solution.

// TypeScript program for
// Find the Lowest Common Ancestor (LCA)
// in a Binary Search Tree

// Tree Node
class TreeNode
{
	public data: number;
	public left: TreeNode;
	public right: TreeNode;
	constructor(data: number)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	public root: TreeNode;
	public status: boolean;
	constructor()
	{
		this.root = null;
		this.status = false;
	}
	// insert a element
	public addNode(data: number)
	{
		// Create a new node
		var node = new TreeNode(data);
		if (this.root == null)
		{
			// When adds a first node in bst
			this.root = node;
		}
		else
		{
			var find = this.root;
			// Add new node to proper position
			while (find != null)
			{
				if (find.data >= data)
				{
					if (find.left == null)
					{
						// When left child empty
						// So add new node here
						find.left = node;
						return;
					}
					else
					{
						// Otherwise
						// Visit left sub-tree
						find = find.left;
					}
				}
				else
				{
					if (find.right == null)
					{
						// When right child empty
						// So add new node here
						find.right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find.right;
					}
				}
			}
		}
	}
	// Find LCA
	public findLCA(head: TreeNode, x: number, y: number)
	{
		if (head != null && this.status == false)
		{
			if (head.data > x && head.data > y)
			{
				this.findLCA(head.left, x, y);
			}
			else if ((head.data < x && head.data < y))
			{
				this.findLCA(head.right, x, y);
			}
			else
			{
				console.log("LCA (" + x + "," + 
                            y + ") : " + head.data);
				this.status = true;
			}
		}
	}
	// Setup to find the lowest lowest common ancestor
	public lca(x: number, y: number)
	{
		if (this.root == null)
		{
			//When BST are have no elements
			console.log("Empty Binary Search Tree");
		}
		else
		{
			this.status = false;
			// Assume that given x and y are exist in BST
			this.findLCA(this.root, x, y);
			if (this.status == false)
			{
				// When x and y are not exist in BST
				console.log("No LCA of node (" + 
                            x + "," + y + ") ");
			}
		}
	}
	public static main()
	{
		var tree = new BinarySearchTree();
		/*
		        7
		       / \ 
		      /   \
		     4     10
		    / \   / \
		   3   6 8   11
		      /   \   
		     5     9   
		*/
		tree.addNode(7);
		tree.addNode(4);
		tree.addNode(3);
		tree.addNode(6);
		tree.addNode(10);
		tree.addNode(8);
		tree.addNode(11);
		tree.addNode(9);
		tree.addNode(5);
		// Test Case A
		tree.lca(5, 9);
		// Test Case B
		tree.lca(9, 11);
		// Test Case C
		tree.lca(3, 4);
	}
}
BinarySearchTree.main();
/*
 file : code.ts
 tsc --target es6 code.ts
 node code.js
 */

Output

LCA (5,9) : 7
LCA (9,11) : 10
LCA (3,4) : 4




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