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: Node which connects to the child
• Child: A node that is connected by another node is a child.
• Root: Topmost Node

• 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.

• Leaf/External Node: Nodes with no children
• Internal Node: Nodes with at least one child.
• Degree: Number of direct children (for a node)

• 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