26. DSA with C++ - Binary trees and their properties

Binary trees and their properties

Definition:

A binary tree is a type of tree data structure in which each node can have at most two child nodes, referred to as the le child and the right child.

1. Root: The root is the topmost node of the binary tree. It serves as the starting point for traversing the tree and does not have a parent node.
2. Node: A node represents an element in the binary tree. Each node contains a value or additional information and may have at most two child nodes.
3. Parent, Left Child, and Right Child: Nodes in a binary tree have a hierarchical relationship. A node that is connected to another node is called its parent, and the node it is connected to is called its child. A binary tree node can have a left child and/or a right child.
4. Leaf: A leaf node, also known as a terminal node or external node, is a node that does not have any child nodes.
5. Internal Node: An internal node is a node that has at least one child node.
6. Height: The height of a binary tree is the length of the longest path from the root to a leaf. It represents the maximum number of edges in any path from the root to a leaf node.
7. Depth: The depth of a node in a binary tree is the number of edges from the root to that node. The root node has a depth of 0.
8. Full Binary Tree: A binary tree is considered full if every node has either 0 or 2 child nodes. In other words, there are no nodes with only one child.
9. Complete Binary Tree: A complete binary tree is a binary tree in which all levels, except possibly the last, are completely filled, and all nodes are as far left as possible.
10. Balanced Binary Tree: A balanced binary tree is a binary tree in which the heights of the left and right subtrees of every node differ by at most one. Common examples include AVL trees and red-black trees.

Binary trees are widely used in various applications, including binary search trees, expression trees, binary heaps, and Huffman coding, among others. They provide efficient data organization and enable efficient searching, insertion, and deletion operations.