YouTipDsa Tree
## Tree Structure
A tree is a **non-linear** data structure that mimics the branching hierarchy of natural trees. Unlike linear structures such as arrays and linked lists, where elements are arranged sequentially, in a tree, the data elements (called **nodes**) have a clear one-to-many hierarchical relationship.
The **tree structure** resembles an actual tree:
* **Root Node**: The topmost node of the tree, which has no parent.
* **Child Node**: Nodes that branch out from a given node.
* **Leaf Node**: Nodes with no children, similar to leaves on a tree.
* **Path**: A route from one node to another.
* **Depth**: The length of the path from the root to the node.
* **Height**: The length of the path from the node to the furthest leaf node.
**Real-life Analogy**:
* **Family Tree**: Grandparents → Parents → Children → Grandchildren
* **Organizational Chart**: CEO → Directors → Managers → Employees
* **File System**: Root Directory → Subdirectories → Files
* **Book Classification**: General Category → Subcategories → Specific Books
| Structure Type | Search Efficiency | Insertion Efficiency | Deletion Efficiency | Ordered |
| --- | --- | --- | --- | --- |
| Array | O(n) | O(n) | O(n) | No |
| Linked List | O(n) | O(1) | O(1) | No |
| Hash Table | O(1) | O(1) | O(1) | No |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | Yes |
### Basic Terminology
Before diving deeper, let's familiarize ourselves with some basic terms related to trees:
!(#)
* **Node**: Each element in a tree. It contains stored data and links to its child nodes.
* **Root**: The topmost node of the tree, serving as the starting point. Every tree has exactly one root node.
* **Parent & Child**: If a node A connects to a node B below it, then A is the **parent** of B, and B is the **child** of A. One parent can have multiple children.
* **Siblings**: Nodes that share the same parent.
* **Leaf**: A node with no children, also known as a terminal node.
* **Edge**: A line connecting two nodes, representing their relationship.
* **Path**: A sequence of nodes from the root to a specific node.
* **Height**: The number of edges on the longest path from a node to its furthest leaf node. The height of the tree is the height of the root node.
* **Depth**: The number of edges on the path from the root to a node. The depth of the root is 0.
* **Level**: All nodes at the same depth belong to the same level. The root is at level 0.
### Basic Properties of Trees
1. **Unique Path**: There exists exactly one path between any two nodes in a tree.
2. **N Nodes, N-1 Edges**: A tree with N nodes has exactly N-1 edges.
3. **No Cycles**: There are no cycles in a tree (i.e., starting from a node and following edges, you cannot return to that node).
* * *
## Why Do We Need Trees? — Advantages and Applications of Trees
You might wonder why we need trees when we already have arrays and linked lists. The answer lies in efficiency.
* **Array**: Fast search (via index), but slow insertion and deletion (requires moving many elements).
* **Linked List**: Fast insertion and deletion, but slow search (requires traversal from head).
* **Tree (especially Binary Search Tree)**: Maintains data order while providing much faster search speed than linked lists and more efficient insertions/deletions than arrays.
**Practical Applications**:
* **File Systems**: Folders and files in computers are organized in a tree-like structure.
* **Database Indexes**: B-trees and B+ trees are core data structures for efficient database queries.
* **Organizational Charts**: Hierarchical management in companies or departments.
* **Decision Trees**: Classification models used in artificial intelligence and machine learning.
* **HTML DOM**: The Document Object Model of web pages is a tree.
* * *
## Binary Tree: The Most Important Member of the Tree Family
A binary tree is a tree where each node has at most two children, typically referred to as the **left child** and the **right child**. It serves as the foundation for many powerful tree structures like Binary Search Trees, Heaps, and AVL Trees.
Basic structure:
!(#)
### Basic Terminology of Binary Trees
| Term | Definition | Real-life Analogy |
| --- | --- | --- |
| **Node** | Basic unit containing data and pointers | A person in a family |
| **Root Node** | Topmost node of the tree | An ancestor in a family |
| **Parent Node** | A node with children | Parent |
| **Child Node** | A node pointed to by a parent | Child |
| **Sibling Nodes** | Nodes sharing the same parent | Siblings |
| **Leaf Node** | A node with no children | Someone without descendants |
| **Depth** | Number of edges from root to node | Generational count |
| **Height** | Number of edges from node to furthest leaf | Generations since that person |
### Types of Binary Trees
| Type | Characteristics | Time Complexity | Use Cases |
| --- | --- | --- | --- |
| **General Binary Tree** | Each node has at most 2 children | O(n) | Expression trees |
| **Full Binary Tree** | Each node has either 0 or 2 children | O(n) | Huffman coding |
| **Complete Binary Tree** | Except for the last level, all levels are full | O(n) | Heap implementation |
| **Binary Search Tree** | Left < Root Left -> Right)**
* First visit the root node, then recursively perform pre-order traversal on the left subtree, followed by recursive pre-order traversal on the right subtree.
* **Application**: Copying a tree, generating prefix expressions.
2. **In-order Traversal (Left -> Root -> Right)**
* First recursively perform in-order traversal on the left subtree, then visit the root node, and finally recursively perform in-order traversal on the right subtree.
* **Application**: In a **binary search tree**, in-order traversal outputs all values in **ascending order**.
3. **Post-order Traversal (Left -> Right -> Root)**
* First recursively perform post-order traversal on the left subtree, then recursively perform post-order traversal on the right subtree, and finally visit the root node.
* **Application**: Deleting a tree, calculating directory size.
4. **Level-order Traversal (By Level, Left to Right)**
* Start from the root node and visit nodes level by level.
* **Application**: Processing data by levels (e.g., printing organizational charts). Usually implemented using a **queue**.
!(#)
**Example**: For the binary tree shown above, the traversal results are:
1
/
2 3
/
4 5 6
* **Pre-order**: 1, 2, 4, 5, 3, 6
* **In-order**: 4, 2, 5, 1, 3, 6
* **Post-order**: 4, 5, 2, 6, 3, 1
* **Level-order**: 1, 2, 3, 4, 5, 6
* * *
## Practice: Implementing a Binary Tree in Python
Enough theory—let's get coding! We'll implement a simple binary tree node class and complete insertion and traversal operations.
### Step 1: Define the Node Class
Each node needs to store data and point to its left and right children.
## Example
```python
class TreeNode:
"""Binary Tree Node Class"""
def __init__(self, value):
self.value = value # Data stored in the node
self.left = None # Points to the left child
self.right = None # Points to the right child
def __str__(self):
"""For easy printing of node information"""
return f"Node({self.value})"
### Step 2: Build an Example Tree
Let’s manually construct the tree from the previous example image.
## Example
```python
# Create nodes
root = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)
# Build connections
root.left = node2
root.right = node3
node2.left = node4
node2.right = node5
node3.right = node6
print(f"Root node: {root}")
print(f"Left child of root: {root.left}")
print(f"Right child of root: {root.right}")
### Step 3: Implement Traversal Algorithms (Recursive Version)
Recursion is the most intuitive way to implement tree traversals.
## Example
```python
def preorder_traversal(node):
"""Pre-order traversal: Root -> Left -> Right"""
if node is None:
return
print(node.value, end=' ') # 1. Visit root node
preorder_traversal(node.left) # 2. Traverse left subtree
preorder_traversal(node.right) # 3. Traverse right subtree
def inorder_traversal(node):
"""In-order traversal: Left -> Root -> Right"""
if node is None:
return
inorder_traversal(node.left) # 1. Traverse left subtree
print(node.value, end=' ') # 2. Visit root node
inorder_traversal(node.right) # 3. Traverse right subtree
def postorder_traversal(node):
"""Post-order traversal: Left -> Right -> Root"""
if node is None:
return
postorder_traversal(node.left) # 1. Traverse left subtree
postorder_traversal(node.right) # 2. Traverse right subtree
print(node.value, end=' ') # 3. Visit root node
print("n--- Traversal Demo ---")
print("Pre-order result:", end=' ')
preorder_traversal(root) # Output: 1 2 4 5 3 6
print("nIn-order result:", end=' ')
inorder_traversal(root) # Output: 4 2 5 1 3 6
print("nPost-order result:", end=' ')
postorder_traversal(root) # Output: 4 5 2 6 3 1
### Step 4: Implement Level-order Traversal (Using Queue)
Level-order traversal requires the FIFO property of queues.
## Example
```python
from collections import deque
def level_order_traversal(root):
"""Level-order traversal using a queue"""
if root is None:
return
queue = deque() # Initialize queue with root node
while queue:
current_node = queue.popleft() # 1. Remove node from front of queue
print(current_node.value, end=' ') # 2. Visit the node
# 3. Add children (if exist) to the back of the queue
if current_node.left:
queue.append(current_node.left)
if current_node.right:
queue.append(current_node.right)
print("nLevel-order result:", end=' ')
level_order_traversal(root) # Output: 1 2 3 4 5 6
* * *
## Exercises and Challenges
Congratulations on completing the basics! To truly master trees, hands-on practice is essential.
### Exercise 1: Calculate Tree Height
Write a function `tree_height(node)` that takes the root node of a tree and returns its height (for an empty tree, define height as -1 or 0 — conventionally acceptable; here we define it as edge count).
**Hint**: Tree height = 1 + max(left subtree height, right subtree height). This is a classic recursive problem.
### Exercise 2: Search Value in Binary Tree
Write a function `search_in_tree(node, target_value)` that searches whether a node with value equal to `target_value` exists in the given binary tree. Return `True` if found, otherwise `False`.
**Hint**: You can use any traversal method and compare values during node visits.
### Challenge: Binary Search Tree (BST)
This is a classic variant of binary trees. In a binary search tree, for any node:
* All values in its **left subtree** are **less than** the node's value.
* All values in its **right subtree** are **greater than** the node's value.
Your challenge is:
1. Implement the `insert_into_bst(root, value)` function to insert a value into the correct position in a binary search tree.
2. Implement the `search_in_bst(root, value)` function to perform efficient search using BST properties (average time complexity O(log N)).