Duration : 00:05:00

The binary tree is a specialized version of the general tree. A data structure in which each node has up to two children. It allows for faster insertion and deletion than linked lists and arrays. It is a flexible method of storing and transferring data.

A binary tree is represented by a pointer to the root node, which is at the top. If the tree is empty, the root value is null. Each node in a Binary Tree has three elements:

- Data
- Pointer to the left child
- Pointer to the right child

**Node**: In a binary tree, a node is a data element with both left and right child addresses.**Root**: The highest node and starting point of a binary tree, with at most one occurrence.**Parent Node**: A non-root node having a following node.**Child Node**: A node that has a preceding node, which could be either parent or child.**Leaf Node**: In a binary tree, a leaf node is the terminal node that has no offspring.**Internal Node**: An internal node has at least one child in a binary tree.**Tree Depth**: The length of the binary tree's longest root-to-leaf path.**Tree Height**: Tree height is the number of edges connecting the lowest node to the root of a binary tree.

- Full/ proper/ strict Binary Tree
- Complete Binary Tree
- Perfect Binary Tree
- Degenerate Binary Tree
- Balanced Binary Tree

Each node has either 0 or 2 offspring, guaranteeing that each level is filled and that depth remains consistent.

All levels are completed, except for the last level, which is filled from left to right.

Each internal node has two offspring, and all leaf nodes are at the same level, resulting in a balanced and entire tree.

A tree in which each parent node has only one child, resulting in a linked list-like structure.

A tree in which the height difference between each node's left and right subtrees is no greater than one, allowing for efficient searching and insertion.

- Binary Search Tree
- AVL Tree
- Red Black Tree
- B Tree
- B+ Tree
- Segment Tree

The left node's value must be less than the parent node, while the right node's value must be greater.

A self-balancing binary search tree in which the difference between the heights of the left and right subtrees for every node is less than one.

This is a self-balancing binary search tree in which each node has an extra bit, which is commonly understood as the color (red or black). These colors keep the tree balanced during insertions and deletions.

It has a predetermined maximum degree (or order), which limits the number of child nodes a parent node can have. Each node in a B-tree can contain several child nodes and keys for indexing and locating data.

This is a type of B-tree with a fixed maximum degree. on a B+ tree, all data items are stored on the leaf nodes, whereas the inside nodes simply carry keys used to index and locate the data items.

A tree data structure that stores information about intervals, or segments.

All operations on the Binary Tree have a space complexity of O(N).

**Search**: Binary search methods use binary trees to search efficiently.**Sort**: Binary trees provide for efficient sorting algorithms such as tree sort and heap sort.**Database**: Binary trees hold data in databases, with each node representing a record, allowing for scalable and efficient searches.**File Systems**: Binary trees are used to represent directories or files.**Compression**: Huffman coding uses binary trees to compress data based on character frequency.**Decision Trees**: Binary trees function as decision trees.**Game AI**: Binary trees are used in game AI to represent alternative moves and discover the best strategies.

**Efficient Search**: Binary trees excel in binary search.**Ordered Traversal**: Binary trees enable ordered traversal.**Memory Efficiency**: Binary trees are memory efficient.**Ease of Implementation**: Binary trees are simple to implement and commonly utilized.

**Limited Structure**: Binary trees have two-child nodes, which limits their structure.**Unbalanced Trees**: Poor balance causes inefficient searches, especially when dealing with non-random data.**Space Inefficiency**: Binary trees waste space since they have two child pointers per node.**Slow Worst-Case**: Degenerate trees slow down searches to O(n) in the worst-case situation.**Complex Balancing**: AVL or red-black tree balancing might be complicated and ineffective for all applications.