Trees & BST

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n$-th vertex in this BFS traversal, then the maximum possible value of $n$ is ________.

Consider the following New-order strategy for traversing a binary tree: • Visit the root; • Visit the right subtree using New-order; • Visit the left subtree using New-order; The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ˆ 6 7 * 1 + - is given by:

The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is ________. *Note: The height of a tree with a single node is 0.*