Discuss following with reference to trees: i) Height of tree ii) Expression tree iii) Complete Binary tree iv) Sibling v) Full Binary tree vi) Path length vii) External Node viii) Internal Node ix) Degree of vertex x) Acyclic Graph

Q.) Discuss following with reference to trees: i) Height of tree ii) Expression tree iii) Complete Binary tree iv) Sibling v) Full Binary tree vi) Path length vii) External Node viii) Internal Node ix) Degree of vertex x) Acyclic Graph

 Subject: Data Structures

i) Height of a Tree:

  • The height of a tree is the maximum number of edges from the root node to the farthest leaf node, or, equivalently, the maximum level of the tree.
  • Often denoted as 'h'.
  • All nodes are assigned a level from '0' to 'h'. The root node is at level '0'.

ii) Expression Tree:

  • A tree structure that represents an arithmetic expression.
  • Each internal node holds an operator (+, -, *, /), and its children hold operands.
  • Expression trees are used in compilers to represent the structure of expressions.

iii) Complete Binary Tree:

  • A binary tree in which every level is completely filled, except for the last level, which may be filled partially.
  • Has the maximum number of nodes possible for a given height.
  • Used to optimize data retrieval and storage efficiency.

iv) Sibling:

  • Two nodes that have the same parent in a tree.
  • Siblings are also called 'brother' and 'sister' nodes.

v) Full Binary Tree:

  • A binary tree in which every node has either zero or two children.
  • Also known as a 'proper binary tree or '2-tree'.
  • Used in various applications, including binary search trees and Huffman coding.

vi) Path Length:

  • The sum of the lengths of all paths from the root node to each leaf node in a tree.
  • Often used to measure the efficiency and balance of a tree.

vii) External Node:

  • A node in a tree that has no children.
  • Also known as a leaf node.
  • Leaf nodes contain actual data values.

viii) Internal Node:

  • A node in a tree that has at least one child.
  • Also known as a 'branching node'.
  • Internal nodes do not contain actual data values, but rather information related to the structure of the tree.

ix) Degree of Vertex:

  • The degree of a vertex is the number of children of that vertex.
  • In a binary tree, the degree of a vertex can be either '0', '1', or '2'.

x) Acyclic Graph:

  • A directed graph in which no cycles exist.
  • Can be represented as a tree by orienting all edges away from the root node.
  • Used to represent hierarchical structures, such as organizational hierarchies or file systems.