Hello, I need help understanding this Question. I do not know where to even begin.
30. Suppose that, during a preorder traversal of a binary tree T, we write down a 1 for each interval vertex and a 0 for each leaf in the traversal, building a sequence of 1s and 0s. If T has n leaves, the sequence will have n 0s and n – 1 1s. We call this sequence the characteristic sequence of T. (Such a sequence determines a unique tree.)
(a) Find the binary tree with the characteristic sequence 110100110100100.
(b) Prove that the last two digits in any characteristic sequence are 0s (assuming n > 2).
(c) Prove that a binary sequence with n 0s and n – 1 1s, for some n, is a characteristic sequence of some binary tree if and only if the first k digits of the sequence contain at least as many 1s as 0s, for 1 < k < 2n – 2.
Thank you
30. Suppose that, during a preorder traversal of a binary tree T, we write down a 1 for each interval vertex and a 0 for each leaf in the traversal, building a sequence of 1s and 0s. If T has n leaves, the sequence will have n 0s and n – 1 1s. We call this sequence the characteristic sequence of T. (Such a sequence determines a unique tree.)
(a) Find the binary tree with the characteristic sequence 110100110100100.
(b) Prove that the last two digits in any characteristic sequence are 0s (assuming n > 2).
(c) Prove that a binary sequence with n 0s and n – 1 1s, for some n, is a characteristic sequence of some binary tree if and only if the first k digits of the sequence contain at least as many 1s as 0s, for 1 < k < 2n – 2.
Thank you
Attachments
Last edited by a moderator: