Preorder Traversal: find binary tree w/ char. seq. 110100110100100

Anviori

New member
Joined
Mar 2, 2016
Messages
2
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
 

Attachments

  • Capture.jpg
    Capture.jpg
    49.3 KB · Views: 9
Last edited by a moderator:
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

Do you understand the "terms" used in this problem?

If you don't - which terms are confusing to you?
 
Last edited by a moderator:
Top