Trees

Trees are ADTs that simulate hierarchical tree structures, composed of a root value and subtrees based on parent-child relationships, and are a collection of interconnected nodes.

One of the crucial attributes of a tree is that it is a recursively defined self-referential data structure. Put simply, in a tree, a child is also a tree, and its child is also a tree. It's commonly said to be composed of subtrees.

Tree Terminology

Reference: https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/

• Degree: The number of child nodes.

• Size: The total number of child nodes, including itself.

• Depth: The distance from the root to the current node.

• Height: The distance from the current position to a leaf.

Note: Levels start from 0 at the root node.

Depth vs. Height

Reference: https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height

properties of a node:

• The depth of a node is the number of edges from the node to the tree's root node. A root node will have a depth of 0.

• The height of a node is the number of edges on the longest path from the node to a leaf. A leaf node will have a height of 0.

Properties of a tree:

• The height of a tree would be the height of its root node, or equivalently, the depth of its deepest node.

• The diameter (or width) of a tree is the number of nodes on the longest path between any two leaf nodes. The tree below has a diameter of 6 nodes.

Graph vs. Tree

• Trees do not have cyclic structures.

• Trees have only one-directional arrows pointing from parent nodes to child nodes.

• Each node in a tree has only one parent.

• A tree has only one root.

Binary Trees

Among trees, the most widely used tree data structures are binary trees and binary search trees. If each node has m or fewer children, it's called an m-ary tree (or polynomial tree). Specifically, when m = 2, meaning all nodes have a degree of 2 or less, it is distinctly called a binary tree.

Reference: https://www.geeksforgeeks.org/types-of-trees-in-data-structures/

Types of Binary Trees

Reference: https://dev.to/vladyslavnua/what-is-a-binary-search-tree-9ll

• Full Binary Tree: Every node has either 0 or 2 child nodes.

• Complete Binary Tree: All levels, except possibly the last, are fully filled, and all nodes in the last level are as far left as possible.

• Perfect Binary Tree: Every node has two child nodes, and all leaf nodes are at the same depth or level. As the name suggests, it's the most "perfect" type of tree.

Binary Search Tree (BST)

While a binary tree is a simple tree form where every node has at most two children regardless of sorting, a binary search tree (BST) is a tree where the values of the left and right children are sorted according to the value's magnitude.

Reference: https://www.javatpoint.com/binary-search-tree

In a node's left subtree of the BST, it consists of nodes with values smaller than that of the node, whereas the right subtree of the node consists of nodes with values equal to or larger than that of the node. Therefore, the time complexity for searching in a BST is $O(logn)$.

Self-Balancing Binary Search Tree

A Self-Balancing Binary Search Tree is a node-based binary search tree that maintains a short height automatically during insertions and deletions. It ensures a well-balanced binary tree even in the worst-case scenario.

The performance difference between a balanced and an unbalanced tree is quite significant, so it's essential to maintain as low a height as possible.

Prominent forms of self-balancing binary search trees include the AVL tree and the Red-Black tree. In particular, the Red-Black tree is a frequently used tree form in practice due to its high efficiency.

Tree Traversals

Tree traversal is a form of graph traversal that involves visiting each node in a tree data structure exactly once.

Similar to graph traversal, tree traversal can be achieved using DFS (Depth-First Search) or BFS (Breadth-First Search). Specifically, in binary trees, DFS can be categorized into three methods based on the order in which nodes are visited:

L represents the current node's left subtree, R represents the current node's right subtree, and N represents the current node itself.

1. Preorder Traversal (NLR)

def preorder(node):
    if node is None:
        return
        
    print(node.val)
    preorder(node.left)
    preorder(node.right)

2. Inorder Traversal (LNR)

def inorder(node):
    if node is None:
        return
    
    inorder(node.left)
    print(node.val)
    inorder(node.right)

3. Postorder Traversal (LRN)

def postorder(node):
    if node is None:
        return
    
    postorder(node.left)
    postorder(node.right)
    print(node.val)