1. Tree Terminologies

A tree is a hierarchical, non-linear data structure made up of nodes connected by edges.

Basic Terms:

• Root: First or topmost node in a tree.
• Parent: A node that has children.
• Child: A node that comes from a parent.
• Leaf Node: A node with no children.
• Siblings: Nodes that have the same parent.
• Ancestors: All nodes on the path from a node up to the root.
• Descendants: All nodes below a given node.
• Degree: Number of children a node has.
• Level: The distance from the root (root is level 0 or 1).
• Height: Longest path from a node to a leaf.
• Depth: Distance from the root to a given node.

Binary Tree:

A binary tree is a tree where each node has at most two children (left and right).

Binary Search Tree (BST):

A special type of binary tree where:

• Left child has smaller or equal value than parent
• Right child has greater value than parent