SDE - 1

Given two binary trees T and S, check whether tree S has exactly the same structure and node values with a subtree of T, i.e., check if tree S is a subtree of the tree T.

A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.

You are given an 'N * N' matrix of integers where each row and each column is sorted in increasing order. You are given a target integer 'X'.

Find the position of 'X' in the matrix. If it exists then return the pair {i, j} where 'i' represents the row and 'j' represents the column of the array, otherwise return {-1,-1}

For example:

If the given matrix is:
[ [1, 2, 5],
  [3, 4, 9],
  [6, 7, 10]] 
We have to find the position of 4. We will return {1,1} since A[1][1] = 4.

You are given two Singly Linked Lists of integers, which may have an intersection point.

Your task is to return the first intersection node. If there is no intersection, return NULL.

Example:-

The Linked Lists, where a1, a2, c1, c2, c3 is the first linked list and b1, b2, b3, c1, c2, c3 is the second linked list, merging at node c1.

You are given a binary search tree and an integer ‘S’. Your task is to find all the pairs of nodes in the BST which sum to the value ‘S’. If no such pair exists, then print -1 - 1.

Note:

You can use extra space of the order of not more than O(log n).

A binary search tree (BST) is a binary tree data structure which has the following properties.
• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

Note:

1. All the elements of the Binary Search Tree are unique.
2. You can’t use the same node value/element of BST twice.

You have been given a binary tree of integers.

Your task is to check if it is a binary heap tree or not.

Note:

A binary tree is a tree in which each parent node has at most two children. 

A binary heap tree has the following properties. 
1. It must be a complete binary tree. In the complete binary tree every level, except the last level, is completely filled and the last level is as far left as possible.

2. Every parent must be greater than its all children nodes.

For example:

Consider this binary tree:

Figure 1 is a complete binary tree because every level, except the last level, is completely filled and the last nodes are as far left as possible, and the level has 2 nodes both on the left side.

Figure 2 is not a complete binary tree because level 2 (level is 0 based) is not completely filled means the right child of the node (36) is missing.
There is another reason, in the last level, there can be one another node in between node (1) and node (14) to make the binary tree as far left as possible.

Note:

1. In the world of programming two types of binary heap tree possible:
   a. Min-heap - if all parents nodes are lesser than its children nodes.
   b. Max-heap - if all parents nodes greater than its children nodes, explained in the above figure-1.

2. In this problem binary heap tree is a binary max-heap tree.

You are given two strings 'S' and 'T' of lengths 'N' and 'M' respectively. Find the "Edit Distance" between the strings.

Edit Distance of two strings is the minimum number of steps required to make one string equal to the other. In order to do so, you can perform the following three operations:

1. Delete a character
2. Replace a character with another one
3. Insert a character

Note:

Strings don't contain spaces in between.