A tree is a hierarchical data structure defined as a collection of nodes. Nodes represent value and nodes are connected by edges. It is identical to representing hierarchy data.

Some Terminology

Parent Root Child in Data Structure and Algorithm DSA
  • Parent: Node which connects to the child
  • Child: A node that is connected by another node is a child.
  • Root: Topmost Node

Siblings Ancestors and decedents in Data Structure and Algorithm - DSA
  • Ancestors: Parent of the parent of the parent and so on.
  • Descendants: Children of Children of Children and so on.
  • Sibling: Nodes belonging to the same parent are siblings.

Internal Node, Leaf Node or External Node in Data Structure and Algorithm - DSA
  • Leaf/External Node: Nodes with no children
  • Internal Node: Nodes with at least one child.
  • Degree: Number of direct children (for a node)

Height Depth in Data Structure and Algorithm - DSA
  • Depth: Number of edges from the root of the node.
  • Height: Number of edges from node to the deepest leaf.
  • Degree of a tree: The degree of a tree is the highest degree of a node among all the nodes present in the tree.
  • Path: The shortest distance between two nodes is called a path.

Types of Tree

  • Binary Tree
  • Binary Search Tree (BST)
  • AVL Tree (Adelson Velsky and Landis - Inventors)
  • B-Tree