Answer: Option 3
Concept:
Tree:
- A tree consists of nodes or vertices that store information and often are labeled by a number or a letter.
- A tree consists of directed edges or undirected edges or both.
- The number of subtrees of a node is called its degree.
- A leaf or a terminal node is a node of degree zero
- A node that is not a leaf is called an interior node or an internal node
- The degree of a node is the number of its children. The degree of a tree is the maximum degree of any of its nodes.
Ancestors of a node in a Tree:
The ancestor nodes of a node are all parent nodes of that particular node.
Explanation:
Consider the following Binary Tree

Every node except the root node (A) has ancestors.
Hence in a tree, the only node that has no ancestors is the root node. (only one node possible)
Additional Information
Full Binary Tree:
A full binary tree is a binary tree in which each node has exactly two or 0 children.
Complete Binary Tree:
A complete binary tree is a binary tree in which
- except last level tree is completely filled.
- The last level is filled from left to right.
Perfect Binary Tree:
A perfect binary tree is a binary tree in which
- all interior node or internal nodes has 2 children.
- all leaves are at the same level.
Balanced Binary Tree:
A Balanced Binary tree is a binary tree in which at any node height of the left subtree and right subtree do not differ by more than 1.
Important Points
1. A tree with n nodes has n - 1 edge.
2. consider a nonempty binary tree with n0 leaves and n2 nodes of degree two (internal nodes). Then
n0 = n2 + 1
Applications of Trees:
1. Huffman Coding
2. Evaluation of Arithmetic Expressions using Expression trees