SDE - 1

You are given two binary trees with 'n' and 'm' nodes respectively.

You need to return true if the two trees are identical. Otherwise, return false.

Example:

For the trees given below:- 

The given trees are identical as:-
1. The number of nodes in both trees is the same. 
2. The number of edges in both trees is the same. 
3. The data for root for both the trees is the same i.e 5. 
4. The data of root -> left (root’s left child) for both the trees is the same i.e 2.
5. The data of root -> right (root’s right child) for both the trees is the same i.e 3.
6. The data of root -> right -> left ( left child of root’s right child) for both the trees is the same i.e 6.
7. Nodes with data 2 and 6 are the leaf nodes for both the binary trees. 

You have to implement an iterator for ‘FLATTEN_2D’ to flatten a two-dimensional array ‘ARR_2D’ into a one-dimensional array ‘ARR_1D’. The iterator should support the following two operations:

‘NEXT’: The first call to ‘NEXT’ should return the first element of ‘ARR_2D’. Each subsequent call should return the next element in the row-wise traversal of ‘ARR_2D’.

‘HAS_NEXT’: It should return ‘true’ if the iteration has more elements to traverse; otherwise, if ‘NEXT’ has traversed the entire ‘ARR_2D’, return ‘false’.

Try to code this using only iterators in C++ or iterators in Java.

The ‘FLATTEN_2D’ object will be instantiated and called as follow:
  FLATTEN_2D it = new FLATTEN_2D(ARR_2d);
  while (it.hasNext()) {
      arr1d.append(it.next());
  }

Example:

ARR_2D = [ 
          [0, 1],
          [2, 3, 4],
          [],
          [5] 
        ]
The computed ‘ARR_1D’ should be as follows:
ARR_1D = [0, 1, 2, 3, 4, 5]
So, the printed output will be: 0 1 2 3 4 5

You are given a string 's', and a dictionary of words 'dict' containing 'n' words. Your task is to add spaces in 's' to form valid sentences, where each word is a word from the dictionary.

You need to return all possible sentences that can be formed using the given dictionary.

Note :

The same word from a dictionary can be used as many times as possible to make sentences.

You have been given a binary matrix 'MAT' containing only 0’s and 1’s of size N x M. You need to find the distance of the nearest cell having 1 in the matrix for each cell.

The distance is calculated as |i1 – i2| + |j1 – j2|, where i1, j1 are the coordinates of the current cell and i2, j2 are the coordinates of the nearest cell having value 1.

Note :

You can only move in four directions which are : Up, Down, Left and Right.

For example :

If N = 3, M = 4

and mat[ ][ ] = { 0, 0, 0, 1,
                  0, 0, 1, 1,
                  0, 1, 1, 0 }

then the output matrix will be

3  2  1  0
2  1  0  0
1  0  0  1

Given a binary tree and the value of two nodes, find the distance between the given two nodes of the Binary Tree.

Distance between two nodes is defined as the minimum number of edges in the path from one node to another.

You are given a 'ROOT' of a binary search tree of integers. The given BST is also a complete binary tree.

Your task is to convert the given binary search tree into a Min Heap and print the preorder traversal of the updated binary search tree.

Note:

Binary Search Tree is a node-based binary tree data structure that has the following properties:

1. The left subtree of a node contains only nodes with keys lesser than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each must also be a binary search tree.

A Binary Heap is a Binary Tree with the following property:

1. It’s a complete tree (all levels are filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.

A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at the root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to Min Heap.

For example:

Given:- BST’s ‘ROOT’ = 4 2 6 -1 -1 -1 -1 
Then the min-heap in pre-order fashion would be 2 4 6.