CSI 2110 Lecture Notes - Lecture 5: Preorder, Tree Traversal

57 views4 pages

Document Summary

Tree traversal: find a tree with the following in-order and post-order traversals. (lvr) (vlr) in-order : fbcdgakpm post-order: fbdgcpkma. In post order, the root always comes last: use in-order to split the root into its 2 subtrees, repeat this process for every subtree in the tree, find a tree with the following in-order and pre-order traversals. Pre order : e o t g o t o v. In order : o g t o e o v t. The post order traversal of this tree is: Note: if you only know one traversal, then there"s no such thing as a unique tree with that order (ie. you need to be provided with two traversals to build a unique tree from them). However, if you only have the post order and pre order traversals you can"t find a unique tree! (you have to have in order as one of the traversals to be able to uniquely identify the tree).

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents

Related Questions