Chapter 19, Problem 16RQE

Program Plan Intro

Binary tree:

• It is a tree data structure which comes under hierarchical data structure.
• It is made of nodes that have a left child, right child and a data element.

Nodes in a binary tree:

• The node which is at the top of a binary tree is called “root node”.
• The element that has children is known as “parent node”.
• The element that is under an element is known as “children”.
• The element or the node that has two children is called “leaves” or “external nodes”.
• In binary tree, each node should have at most two children.

Insertion in a binary tree:

• Check whether a node is empty or not in a tree.
• If the left child is empty, then the new node is inserted as the left child.
• If the right child is empty, then the new node is inserted as the right child.
• Traversing should be done until the left or right node is empty.