The postorder traversal of a binary search tree with integer values produces the following sequence: 7, 12, 25, 47, 89, 55, 42, 17. What is the value of the left child of the root of the tree?
The inorder traversal of a search tree is always the sorted sequence. In this case: 7, 12, 17, 25, 42, 47, 55,
89. From the postorder traversal, we know that 17 is the root of the tree, so the segment 7, 12 corresponds
to the left subtree and the segment 25, 42, 47, 55, 89 corresponds to the right subtree. The postorder
traversal of the left subtree ends with 12, so this is the left child of the root node. Click to Join Our Telegram Group for Latest Update of MOCK TEST
A Binary Search Tree (BST) is made by including each integer in [1,100] exactly once. The depth of a node in the BST is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is_____.
Consider the following function to traverse a search tree t with integer values, where even(m)
returns True if m is an even number and False otherwise.
function strangeOrder(t) {
if (t != NIL) {
if (even(t.value)){
strangeOrder(t.left);
strangeOrder(t.right);
print(t.value);
}
else{
print(t.value);
strangeOrder(t.right);
strangeOrder(t.left);
}
}
}
What is the complexity of this traversal for a binary search tree with n nodes?
Do an inorder traversal , at each node, if both of its children are NULL, print it out. Checking for NULL is constant timeoperation. Must visit each node once. So \Theta (N) for traversal. Hence, ans is \Theta (N). Click to Join Our Telegram Group for Latest Update of MOCK TEST
Two binary search tree t_1 and t_2 are equivalent if they contain exactly the same elements. That is, for all x \in t_1,x \in t_2, and for all y \in t_1, y \in t_1. What is the time complexity of an efficient algorithm to determine if BSTs t_1 and t_2 are equivalent. Assume |t_1|=|t_2|=n.
One solution is to read the elements of each tree into a sorted list using
an in-order walk, and compare the resulting lists for equality. This algorithm runs in
\Theta (n).
Another \Theta (n) solution is to put all of the elements of each tree into a hash table, and
compare the resulting tables. Click to Join Our Telegram Group for Latest Update of MOCK TEST