Question

Suppose that the following elements are added in the specified order to an empty binary search tree: Kirk, Spock, Scotty, McCoy, Chekov, Uhuru, Sulu, Khaaaan! Write the elements of the tree above in the order they would be seen by a pre-order, in-order, and post-order traversal. Type your solutions with the elements separated by spaces and/or commas, such as:

Answer 1

Answer:

Pre-order: Kirk, Chekov, Khaaaan, Spock, Scotty, McCoy, Sulu, Uhuru

In-order: Chekov, Khaaaan, Kirk, McCoy, Scotty, Spock, Sulu, Uhuru

Post-order: Khaaaan, Chekov, McCoy, Scotty, Sulu, Uhuru, Spock, Kirk

Explanation:

The binary search tree is described in the diagram below.

The pre-order traversal of the binary tree gets the root, then the left node and right node. The in-order traversal picks the left node, the root node, and then the right node while the post-order traversal of the binary tree follows the left node, right node, and then the root node.