SDE - 1

You are given a binary search tree of integers with N nodes. You are also given references to two nodes 'P' and 'Q' from this BST.

Your task is to find the lowest common ancestor(LCA) of these two given nodes.

The lowest common ancestor for two nodes P and Q is defined as the lowest node that has both P and Q as descendants (where we allow a node to be a descendant of itself)

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.

For example:

'P' = 1, 'Q' = 3
tree = 2 1 4 -1 -1 3 -1 -1 -1,

The BST corresponding will be- 

Here, we can clearly see that LCA of node 1 and node 3 is 2.

Write an advantage of dynamic allocation algorithms?
Write a difference between internal fragmentation and external fragmentation?
How to recover from a deadlock?

You are given the root node of a binary tree consisting of 'N' nodes. Your task is to return the maximum height difference of the tree.

The height of a Binary Tree is defined as the number of nodes present in the longest path from the root node to any leaf node of the tree. The height difference of a node is equal to the absolute difference of height of the left and right subtree.

For example:

For the given tree,
The maximum height difference is 1. The height difference of node 1 is the absolute difference of the height of subtree with root node 2, and the height of subtree with root node 3, which is 1. Hence the answer is 1. 

Example:

Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be :

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. 

The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Why we cannot use the WHERE clause with aggregate functions like HAVING?
Difference between primary key and unique key and why one should use unique key if it allows only one null ?

I was asked to design Library Management System