What is tree data structure? 🌳

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.

🌳 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
• Lowest Common Ancestor of a Binary Search Tree
• Maximum Depth of Binary Tree
• Balanced Binary Tree
• Diameter of Binary Tree
• Binary Tree Level Order Traversal
• Implement Trie (Prefix Tree)
• Validate Binary Search Tree
• Lowest Common Ancestor of a Binary Tree
• Binary Tree Right Side View
• Serialize and Deserialize Binary Tree
• Construct Binary Tree from Preorder and Inorder Traversal
• Minimum Height Trees
• Kth Smallest Element in a BST

Links -

• More questions relevant to BST :
• Run your c++ code online : https://ideone.com/
• Structures in C++