Chapter 8, Problem 48E

Program Plan Intro

Binary search tree:

• Binary search tree is a tree; the nodes are sorted in the semantic order.
• Binary search tree nodes can have zero, one, or two children.
• Node without children is called a leaf or end node.
• A node that does not have a superior node is called a root node or starting node.
  • In binary search tree, the left subtree contains the nodes lesser than the root node.
  • The right subtree contains the nodes greater than the root node.
• The binary search will performed until finding a search node or reaching the end of the tree.

Explanation of Solution

Print the elements of binary search tree:

Step 1:

• Initially, the algorithm traverses the tree by the order left node, root node, and right node.
• Here, the root node of the tree is 50.
  • It contains left node value as 26 in the first level.
  • The node 26 contains left node 12 in the second level.
  • Next, the node 12 contains left node 11 in the third level.
  • Next, the node 11 contains left node 9 in the fourth level.
  • Finally, the node 9 reaches the last left node 2 in the tree.
  • Node 2 does not have left and right child, so it prints the current node element “2”.
  • Then, it print the root node element “9”.
  • Finally, it print the right node element “10”.

Step 2:

As per the algorithm, the “print()” method reaches the left node 11. So, it print the current node element “11”.

• Then it print the root node element “12”.

As per the algorithm, the “print()” method reaches the right node 25 but the node contains the left node 16. So, it print the current node element “16”.

• Then it print the right node element “17”.
• Finally, it print the element “25”.