🌲🌳 DSA using Python: Tree 🌳🌲

 Follow Me

Tree Data Structure

✅ Tree Data Structure:

A tree is a non-linear, hierarchical data structure consisting of nodes. It has a root node and child nodes, and it does not contain any cycles. Each node contains data and references to its child nodes.

🔑Syntax of Tree Data Structure:

class Node:
    def __init__(self, data):
        self.data = data
        self.children = []
root = Node(10)
child1 = Node(5)
child2 = Node(15)
root.children.append(child1)
root.children.append(child2)

☘Three Main Types of Trees:

• Binary Tree     👈 Click Here
• Binary Search Tree     👈 Click Here
• Heap Tree     👈 Click Here

💐Basic Terminology in Tree Data Structure:

Term	Description
Node	A single element in a tree containing data.
Root	The topmost node of the tree.
Edge	A link between a parent and a child node.
Parent	A node that has one or more child nodes.
Child	A node that descends from another node (its parent).
Leaf	A node with no children (also called external node).
Sibling	Nodes that share the same parent.
Ancestor	Any node on the path from the root to that node.
Descendant	Any node that is under a particular node.
Degree	Number of children a node has.
Level	Distance from the root node (root is level 0).
Height	Number of edges on the longest path from the node to a leaf.
Depth	Number of edges from the root to the node.
Subtree	A tree formed from a node and its descendants.
Path	A sequence of nodes connected by edges.

🌳 Representation of Tree Data Structure

A tree is a hierarchical structure consisting of nodes connected by edges, and we can represent it in two main ways in programming:

✅ 1. Using Nodes and Pointers (Linked Representation)

🔹In this method, each node contains:

• Data (value)
• Pointer(s) to child node(s)

🔹 Example in Python (Binary Tree):

class Node: def __init__(self, data): self.data = data self.left = None # Left child self.right = None # Right child # Creating nodes root = Node(10) root.left = Node(5) root.right = Node(20)

🔸 Explanation:

• The root node is 10.
• It has two children: 5 (left) and 20 (right).
• This is a Binary Tree, where each node has at most 2 children.

🌳 Representation of a Node in Tree Data Structure

A node is the basic unit of a tree. Each node stores data and references (pointers) to its child nodes. The way a node is represented depends on the type of tree (binary tree, general tree, etc.).

✅ 1. Node Representation in Binary Tree

In a binary tree, each node has at most two children: left and right.

🔹 Python Code Example:

class Node: def __init__(self, data): self.data = data # stores the data self.left = None # points to the left child self.right = None # points to the right child

🔸 Explanation:

• data holds the value.
• left points to the left child node.
• right points to the right child node.

📌 Example of Creating Tree Nodes:

root = Node(10)
root.left = Node(5)
root.right = Node(15)

        10
        /  \
      5   15

✅ 2. Node Representation in General (N-ary) Tree

In a general tree, each node can have multiple children (not limited to 2).

🔹 Python Code Example:

class Node: def __init__(self, data): self.data = data self.children = [] # list to hold all child nodes

🔸 Example:

root = Node('A')
child1 = Node('B')
child2 = Node('C')

root.children.append(child1)
root.children.append(child2)

      A
      / \
    B  C

📝 Summary

Tree Type	Node Representation
Binary Tree	data, left, right pointers
N-ary Tree	data, children[] list of child nodes

🌳 Basic Operations on Tree Data Structure

A tree supports several important operations that allow you to create, navigate, and manage data efficiently.

✅ 1. Insertion

• Add a node to the tree at the correct position.

• In Binary Search Tree, inserted according to value:

  • Left child < parent < Right child.

🔹 Example:

# Insert 5 under 10
root.left = Node(5)

✅ 2. Deletion

• Remove a node from the tree.

• 3 cases in BST:

  • Node is a leaf.

  • Node has one child.

  • Node has two children (replace with inorder successor/predecessor).

✅ 3. Traversal

• Visit all nodes in a specific order.

🔹 Types of Traversal:

Traversal Type	Order
Inorder	Left → Root → Right
Preorder	Root → Left → Right
Postorder	Left → Right → Root
Level-order	Visit level by level (using a queue)

🔸 Inorder Example (BST gives sorted order):

def inorder(node): if node: inorder(node.left) print(node.data) inorder(node.right)

✅ 4. Searching

• Find whether a value exists in the tree.

• In BST: Use value comparison to search faster.

🔸 Example:

def search(node, key): if not node or node.data == key: return node if key < node.data: return search(node.left, key) return search(node.right, key)

✅ 5. Updation (Modification)

• Change the value of a node or restructure the tree if needed.

✅ 6. Height/Depth Calculation

• Height: Max number of edges from root to a leaf.

• Depth: Number of edges from root to the given node.

🔸 Example:

def height(node): if not node: return -1 return 1 + max(height(node.left), height(node.right))

✅ 7. Count Nodes / Leaves

• Total number of nodes or leaf nodes in the tree.

📌 Summary Table

Operation	Purpose
Insertion	Add a node to the tree
Deletion	Remove a node from the tree
Traversal	Visit nodes in a specific order
Searching	Find a node with a specific value
Updating	Modify data in a node
Height/Depth	Measure structure and distance in the tree
Count Nodes	Count total or leaf nodes

🌳 Advantages of Tree Data Structure

Advantage	Explanation
✅ Hierarchical Structure	Represents parent-child relationships naturally (like file systems).
✅ Faster Search	In a Binary Search Tree (BST), search is faster than arrays/linked lists (O(log n) in average).
✅ Efficient Insertion/Deletion	Insert and delete operations can be done efficiently (especially in BST or balanced trees).
✅ Sorted Data Handling	BST and its variants maintain data in a sorted manner automatically.
✅ Flexible Data Organization	Suitable for complex and recursive data (e.g., XML/JSON data, expressions).
✅ Memory Efficient	Unlike arrays, memory is allocated only when nodes are added.
✅ Foundation for Advanced DS	Trees are the basis of heaps, tries, B-trees, segment trees, etc.

❌ Disadvantages of Tree Data Structure

Disadvantage	Explanation
❌ Complex Implementation	Trees (especially balanced ones) are harder to implement than arrays/lists.
❌ Extra Memory Usage	Requires extra pointers or references for child nodes.
❌ Unbalanced Trees = Poor Performance	If not balanced, performance can degrade to O(n) (e.g., in skewed BSTs).
❌ Difficult Debugging/Visualization	Recursive structure can make debugging and visualization harder.
❌ Not Cache-Friendly	Due to non-contiguous memory allocation, trees may not use CPU cache effectively.