2020_1120 Algorithm - Tree

1. Tree: Height of a Binary Tree

  - www.hackerrank.com/challenges/tree-height-of-a-binary-tree/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=trees

int height(Node* root)
{
	if (root == NULL)
		return -1;
	//
	int leftHeight = height(root->left);
	int rightHeight = height(root->right);
	//
	int result = max(leftHeight, rightHeight);
	//
	return (result + 1);
}

 

2. Binary Search Tree : Lowest Common Ancestor

  - www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=trees

Node* lca(Node* root, int v1, int v2)
{
	if (root == nullptr)
		return nullptr;
	//
	if (root->data > v1 && root->data > v2)
		return lca(root->left, v1, v2);
	if (root->data < v1 && root->data < v2)
		return lca(root->right, v1, v2);
	//
	return root;
}

 

3. Tree: Huffman Decoding

  - www.hackerrank.com/challenges/tree-huffman-decoding/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=trees

void decode_huff(Node* root, string s)
{
	Node* temp = root;
	for (int i = 0; i < s.length() + 1; ++i)
	{
		// Check is Leaf
		if (temp->data != NULL)
		{
			std::cout << temp->data;
			temp = root;
		}
		// Set node & Move next
		if (s[i] == '0')
			temp = temp->left;
		else if (s[i] == '1')
			temp = temp->right;
	}
}