Trees

A tree is a non-linear data structureThe organisation and order of information in a text. that consists of a set of connected nodes. Each node in a tree has a value and zero or more children nodes. One of the nodes in the tree is designated as the root node, and the remaining nodes are organized into a hierarchical structure called branches.

There are different types of trees, some of the most common are:

Binary Tree: A tree in which every node has at most two children, called left and right child.

Binary Search Tree: A binary tree where the value of each node is greater than or equal to the values in its left subtree and less than or equal to the values in its right subtree. This structure allows for efficient searching, insertion, and deletion of elements.

AVL Tree: A binary search tree where the difference between the heights of the left and right subtrees of any node is at most 1. This allows for quick insertion and deletion of elements while maintaining a relatively balanced tree.

Trie: A tree-like data structure that is used to storeThe stage where the CPU saves the result of the execution back into memory or registers. a collection of strings. Each node of the trie represents a character of a string, and the path from the root to the node represents a string. Tries are used for efficient searching and insertion of strings.

There are several ways to traverse a tree, some of the most common are:

• In-Order traversal: visits the left subtree, the root, and then the right subtree.
• Pre-Order traversal: visits the root, the left subtree, and then the right subtree.
• Post-Order traversal: visits the left subtree, the right subtree, and then the root.

Insertion and deletion of elements in a tree depends on the type of tree. In a binary search tree, when inserting an element, you start at the root and compare the value of the node with the value you want to insert. If the value is less than the current node, you move to the left child, if it's greater you move to the right child. Repeat this process until you find an empty spot where you can insert the new node. When deleting an element, you first find the node with the value you want to delete, then depending on the number of children of the node, it can be replaced with its in-order successor or in-order predecessor.