Yesterday we were discussing rebuilding a tree from post order and in order traversals.
Today we see if we can rebuild a tree from preorder and post order:
We make the following observations:
1) the roots are found top down by walking the post order list in the reverse manner or the preorder in the forward manner
2) the length of the left subtree for any root in preorder is given by the number of nodes between its position in the postorder and the start for the subtree of the parent.
3) the position of the start of the subtree of the parent is given by the start of the post order or the start of the sibling in the post order depending on whether it is the left or the right subtree
4) In general, we can rebuild the tree if we know the sizes of either left or right subtree consistently. We don't need both but if we do that's great.
5) the length of the right subtree is the distance between the the position of the left sibling and the root in the post order.
6) The subtrees may be null and we just need to be mindful of the size but not need to check it upfront.
7) Since the items 2) and 5) indicate that we need to the postion of a sibling for at least the root of the whole tree to begin with, it is important to identify one of the siblings first.
8) if the element next to the root in pre is the same as the element previous to the same root in post, then one of the subtrees is null.
9) Since we cannot say which of the subtree is null from 8), this problem is not possible to solve.
Consider:
Pre: AB
Post BA
and
Pre: AC
Post: CA
A
B C
D E F G
H I J K L M N O
Pre: A B D H I E J K C F L M G N O
Post: H I D J K E B L M F N O G C A
In: H D I B J E K A L F M C N G O
Here too we see that unless the left subtree and the right subtree are listed once on both sides of the root, the solution becomes difficult. Therefore inorder traversal is needed.
#coding exercise
#codingexercise
int GetMissingSerialNumber(List<int> num)
{
int sum_of_n = num.Count x (numCount + 1)/2;
return sum_of_n-num.sum();
}
The sorting would help narrow down the range with the missing numbers logarithmically if there were more than one.
int binarysearch(List<int> num, int target, int start, int end)
{
assert (start <= end);
int mid = (start + end)/2;
if (num[mid] == target) return mid;
if ( mid == start) return -1;
if (num[mid] < target)
return binarysearch(num, target, mid + 1, end);
else
return binarysearch(num, target, start, mid-1);
}
Today we see if we can rebuild a tree from preorder and post order:
We make the following observations:
1) the roots are found top down by walking the post order list in the reverse manner or the preorder in the forward manner
2) the length of the left subtree for any root in preorder is given by the number of nodes between its position in the postorder and the start for the subtree of the parent.
3) the position of the start of the subtree of the parent is given by the start of the post order or the start of the sibling in the post order depending on whether it is the left or the right subtree
4) In general, we can rebuild the tree if we know the sizes of either left or right subtree consistently. We don't need both but if we do that's great.
5) the length of the right subtree is the distance between the the position of the left sibling and the root in the post order.
6) The subtrees may be null and we just need to be mindful of the size but not need to check it upfront.
7) Since the items 2) and 5) indicate that we need to the postion of a sibling for at least the root of the whole tree to begin with, it is important to identify one of the siblings first.
8) if the element next to the root in pre is the same as the element previous to the same root in post, then one of the subtrees is null.
9) Since we cannot say which of the subtree is null from 8), this problem is not possible to solve.
Consider:
Pre: AB
Post BA
and
Pre: AC
Post: CA
A
B C
D E F G
H I J K L M N O
Pre: A B D H I E J K C F L M G N O
Post: H I D J K E B L M F N O G C A
In: H D I B J E K A L F M C N G O
Here too we see that unless the left subtree and the right subtree are listed once on both sides of the root, the solution becomes difficult. Therefore inorder traversal is needed.
#coding exercise
int GetSmallestNumberListed(string number, int n) // assume unique
{
if (String.IsNullorEmpty(number) || n <= 0) return null;
for (int I =0; I < numbers.Length; I++ )
{
if (Char.IsDigit(numbers[I]) == false)
{
return -1;
}
}
string sorted = number.sort();
int returnLength = number.Length - n;
if (returnLength <= 0) return -1;
sorted = sorted.substring(0, returnLength);
String result = null;
for (int I = 0; I < numbers.Length; I++)
{
var candidate = string.Empty;
if (sorted.Contains(numbers[I]))
{
candidate += numbers[I];
for (int j = I+1; j < numbers.Length; j++)
{
if (sorted.contains(numbers[j]))
{
if (candidate.Length >= returnLength) break;
candidate += numbers[j];
}
}
if (result == null)
{
result = candidate;
}
if (candidate.Length == returnLength && String.CompareOrdinal(
{
result = candidate;
}
}
}
return result;
}
int GetMissingSerialNumber(List<int> num)
{
int sum_of_n = num.Count x (numCount + 1)/2;
return sum_of_n-num.sum();
}
The sorting would help narrow down the range with the missing numbers logarithmically if there were more than one.
int binarysearch(List<int> num, int target, int start, int end)
{
assert (start <= end);
int mid = (start + end)/2;
if (num[mid] == target) return mid;
if ( mid == start) return -1;
if (num[mid] < target)
return binarysearch(num, target, mid + 1, end);
else
return binarysearch(num, target, start, mid-1);
}
