Trees

About

An absctract data type that represents a hierarchical tree structure with a set of connected nodes.

Useful fo represent data in a non-linear form, making them suitable for representing hierarquical relationships.

Each node in the tree can be connected to many children nodes (depending on the type of tree), but must be connected to exactly one parent node.

You may assume that in a Tree with V number of vertices (nodes), it will have $E = V - 1$ amount of E edges. (Because each node will have at least 1 edge, connecting it to it's parent node)

These constraints mean:

• There are no cycles or "loops". (no node can be its own ancestor)

• Each child can be treated like the root node of its own subtree. (Making recursion a useful technique for tree traversal)

Terminology

node	The fundamental unit of the tree that holds data.
edge	The connection between two nodes.
root	The topmost node. (Has depth 0)
leaf	Node without children.
height	The longest path from the root to the deepest leaf.
degree	For a given node, its the number of children. (A leaf has degree of 0)
depth	The number of edges from the root to the node.
level	The same as depth, but it starts the count from 1, instead of 0.

Traversing Trees

There are 3 types of tree traversals. (That depends on when you do the visiting of the node)

• Pre-Order traversal. (Visit the node, then go Left, then go Right)

• In-Order traversal. (Go Left, then visit the node, then go Right)

• Post-Order traversal. (Go Left, then go Right, then visit the node)

Tree Types

Type	Desciption
General Trees	Trees where a node may have any amount of children.
Binary Trees	A tree type in which each node has at most two children. (It may have 0, 1 or 2)
Full Binary Trees	A sub-type where every node has either 0 or 2 children.
Complete Binary Trees	All levels, except possibly the last, are fully filled. All nodes are as far left as possible.
Perfect Binary Trees	All internal nodes have two children. All leaves are at the same level.
Binary Search Tree (BST)	A Binary Tree in which: The left child contains values smaller than the parent. The right child contains values greater than the parent.
Balanced BST	A Binary Tree where the height difference between the left and right subtrees of every node is at most 1.
AVL Tree	A self-balancing Binary Search Tree where the height of the left and right subtrees differ by at most 1.
Red-Black Tree	It is a self-balancing Binary Search Tree with specific coloring rules to maintain balance.
Trie	A General Tree specifically used for efficient retrieval of strings, commonly used in autocomplete features. Each node can have any number of children.
B Trees	Self-balancing Search Trees. B-Trees can have N children.
B+ Trees	Self-balancing Search Trees designed for filesystems and database systems.
Heap	It is a Binary Tree where every child is: Smaller than the current node. (Max Heap) Larger than the current node. (Min Heap)