What is tree data structure? 🌳
Tags: tree, datastructures
Published: 2023-10-17 19:39:21

Today we are going to discuss:

- What is a tree?
- Basic tree terminologies
- Types of trees
- Operations on trees
- Some practice questions

###🌳 What is a tree?

Trees are hierarchical data structures used to organize and represent data in a manner that resembles a tree with a root at the top and branches connecting nodes. Each node can have child nodes, creating a parent-child relationship. 

Tree data structures have various real-world applications:

- **File Explorer**: Trees organize files and folders hierarchically, making it easy to navigate and locate data on your device.
- **Parsers (XML parser)**: Trees structure and interpret data from files like XML, allowing software to understand and process information effectively.
- **Database for Indexing**: Trees enable efficient data storage and retrieval in databases, speeding up searches.
- **DNS (Domain Name System)**: Trees convert domain names into IP addresses, facilitating internet communication.
- **Trie (Autocomplete)**: Trees power autocomplete suggestions in search engines by quickly searching for and suggesting relevant terms or phrases as you type.

![example-of-a-binary-tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7w3271r2r8ehtu6wnw37.png)

###🌳 Basic tree terminologies

- **Parent:** A node in a tree data structure that has one or more child nodes directly connected to it.
- **Child:** A node in a tree data structure that is connected to a parent node.
- **Root:** The topmost node in a tree, serving as the starting point for traversing the structure. It has no parent.
- **Leaf:** A node in a tree that has no children, meaning it is a terminal node.
- **Internal Node:** A node in a tree that is not a leaf, which means it has one or more children.
- **Level:** The position of a node within a tree, with the root node at level 0 and each subsequent level increasing by 1.
- **Sibling:** Nodes that share the same parent in a tree.
- **Degree of a Node:** The number of subtrees (children) connected to a node. Leaf nodes have a degree of 0.
- **Height of a Tree:** The length of the longest path from the root to a leaf node in the tree.
- **Height of a Node:** The length of the longest path from the node to a leaf node in the tree.
- **Depth of a Node:** The length of the path from the root to that node, measured in terms of the number of edges in the path.

###🌳 Types of trees

Now that we know what a tree is, let use look into a few different types of trees. You must have came across a binary tree or a binary search tree.

- **General Tree:** A tree structure where nodes can have any number of children, providing flexibility in organising hierarchical data.

- **Binary Tree:** A tree in which each node can have at most two children, commonly used for efficient data organisation and traversal.

- **Binary Search Tree (BST):** A binary tree where values are organised so that left children are smaller, and right children are equal to or greater than the parent, enabling efficient searching and sorting.

- **AVL Trees:** A self-balancing binary search tree that ensures the height difference between left and right subtrees is kept to a minimum, guaranteeing efficient operations.

- **Red-Black Trees:** Another self-balancing binary search tree that maintains balance by using colored nodes and performing rotations, suitable for a variety of applications.

- **N-ary Trees:** Trees where nodes can have more than two child nodes, allowing for versatile data representation.

- **B-Trees:** Self-balancing trees used for managing large datasets, frequently employed in databases and file systems.

- **B+ Trees:** A variant of B-trees with enhanced properties, particularly useful for indexing large amounts of data in databases.

- **Trie (Prefix Tree):** A tree structure optimized for storing and searching strings, commonly employed in applications such as autocomplete and spell-checking.

- **Ternary Tree:** A tree with nodes that have exactly three children, often used in specialised scenarios requiring a three-way decision structure.

- **Segment Tree:** A binary tree structure designed for efficient range queries, especially useful for finding intervals or segments that contain a given query point, offering fast retrieval in O(log n + k) time, where k represents the number of retrieved intervals or segments.

###🌳 Operations on trees

We can perform a variety of operations on trees. Let us have a look on some of the common ones.

- **Insertion:** Add a new node with a given value to the tree.
- **Deletion:** Remove a specific node (and its subtree) from the tree.
- **Search:** Find a specific node with a given value in the tree.
- **Traversal:**
   - **Inorder:** Visit nodes in sorted order (for binary search trees).
   - **Preorder:** Visit the current node before its children.
   - **Postorder:** Visit the current node after its children.
   - **Level-order:** Visit nodes level by level, starting from the root.
- **Find Minimum/Maximum:** Find the node with the smallest or largest value in the tree.
- **Balancing:** Rebalance the tree to ensure that it maintains a specific structure, such as in AVL trees or Red-Black trees.
- **Height Calculation:** Calculate and return the height (or depth) of the tree.
- **Count Nodes:** Count and return the number of nodes in the tree.
- **Diameter Calculation:** Find the length of the longest path between any two nodes in the tree.
- **Lowest Common Ancestor (LCA):** Find the lowest common ancestor of two nodes in the tree.
- **Checking for Balance:** Verify whether the tree is balanced, ensuring the heights of subtrees do not differ by more than a certain threshold.
- **Serialization and Deserialization:** Convert the tree into a serial format for storage or transmission, and then reconstruct the tree from the serialized data.
- **Prefix Search (in Tries):** Search for words or strings based on a common prefix in a Trie data structure.
- **Traversal for Specific Orderings:** Perform various tree traversals (e.g., in-order, preorder, postorder) with specific requirements or rules for processing nodes.
- **Pruning:** Remove specific nodes or subtrees from the tree based on certain conditions or criteria.

###🌳 Some practice questions

To understand trees better and develop an intuition for solving tree problems, I recommend the following problems.

Before anything else, Implement a simple BST with the functions to create node, insert node, delete node and tree-traversal, after that do the following questions:

- [Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree)
- [Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree)
- [Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree)
- [Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree)
- [Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree)
- [Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal)
- [Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree)
- [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree)
- [Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree)
- [Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view)
- [Serialize and Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree)
- [Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal)
- [Minimum Height Trees](https://leetcode.com/problems/minimum-height-trees)
- [Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst)

### Links  -

- [More questions relevant to BST ](https://leetcode.com/tag/binary-search-tree/): 
- Run your c++ code online : https://ideone.com/
- [Structures in C++](https://www.w3schools.com/cpp/cpp_structs.asp)