N-ary Trees
Introduction to Generic Trees (N-ary Trees)
An N-ary trees is a data structure that generalizes the concept of a binary tree to include any number of child nodes at each level. In other words, an n-ary tree is a tree data structure in which each node can have up to ‘n’ children.
In other words, an N-ary Trees is a tree data structure in which each node can have up to ‘n’ children. These trees are particularly useful in various applications where data needs to be organized hierarchically, and the number of child nodes for each parent can vary.
What are N-ary Trees?
An N-ary tree permits a node to have ‘n’ children, as the name implies, in contrast to the more prevalent binary trees, which allow a node to have at most two children. This characteristic makes N-ary trees more complex than binary trees.
Example
For storing the address of the node(children) of N-ary Tree, we can use traditional array or linked list. But at the same time, these types of data structure has disadvantages :
- In a linked list, accessing a child’s address at random positions is not efficient due to the lack of direct indexing.
- In contrast, an array allows for random access of child addresses, but it has a limitation in that it can only store a fixed number of children’s addresses.
Hence, we can use Dynamic Arrays for storing the address of the children.
Dynamic Array Initialization :
class Node:
def __init__(self,data):
self.data=data
self.children=[]
Why we use Dynamic Arrays in N-ary Trees?
When it comes to efficiently traversing nodes, dynamic arrays are often a better choice than linked lists or traditional arrays.
Here’s why dynamic arrays are preferred:
N-ary Tree Traversal
The most common traversal methods for N-ary trees are:
- Preorder Traversal
- Postorder Traversal
- Level-Order Traversal
1. Preorder Traversal
In a preorder traversal, you visit the current node before its children.
Algorithm:
The order of operations is as follows:
- Visit the current node (process its data).
- Recursively traverse all its children from left to right.
Code :
def preorder_traversal(node):
if node is not None:
process_node(node)
for child in node.children:
preorder_traversal(child)
2. Postorder Traversal
In a postorder traversal, you visit the current node after its children.
Algorithm:
The order of operations is as follows:
- Recursively traverse all children from left to right.
- Visit the current node (process its data).
Code :
def postorder_traversal(node):
if node is not None:
for child in node.children:
postorder_traversal(child)
process_node(node)
3. Level-Order Traversal (Breadth-First Traversal):
In a level-order traversal, you visit nodes level by level, starting from the root and moving from left to right. This traversal is often implemented using a queue to maintain the order.
from collections import deque
def level_order_traversal(root):
if root is None:
return
queue = deque([root])
while queue:
node = queue.popleft()
process_node(node)
for child in node.children:
queue.append(child)
N-ary Tree Implementation
Initializing an n-ary tree involves creating a structure to represent the nodes and their relationships. You can use a simple Python class to define the basic structure of the n-ary tree.
Code :
class TreeNode:
def __init__(self, data):
self.data = data
self.children = []
class NaryTree:
def __init__(self, root_data):
self.root = TreeNode(root_data)
def add_child(self, parent, child_data):
child = TreeNode(child_data)
parent.children.append(child)
def remove_child(self, parent, child_data):
for child in parent.children:
if child.data == child_data:
parent.children.remove(child)
return
def find_node(self, data, current_node=None):
if current_node is None:
current_node = self.root
if current_node.data == data:
return current_node
for child in current_node.children:
found_node = self.find_node(data, child)
if found_node:
return found_node
def preorder_traversal(self, node=None):
if node is None:
node = self.root
result = []
result.append(node.data)
for child in node.children:
result.extend(self.preorder_traversal(child))
return result
def postorder_traversal(self, node=None):
if node is None:
node = self.root
result = []
for child in node.children:
result.extend(self.postorder_traversal(child))
result.append(node.data)
return result
if __name__ == "__main__":
nary_tree = NaryTree("A")
nary_tree.add_child(nary_tree.root, "B")
nary_tree.add_child(nary_tree.root, "C")
nary_tree.add_child(nary_tree.root.children[0], "D")
nary_tree.add_child(nary_tree.root.children[0], "E")
nary_tree.add_child(nary_tree.root.children[1], "F")
nary_tree.add_child(nary_tree.root.children[1], "G")
print("Preorder Traversal:", nary_tree.preorder_traversal())
print("Postorder Traversal:", nary_tree.postorder_traversal())
Output :
Preorder Traversal: ['A', 'B', 'D', 'E', 'C', 'F', 'G'] Postorder Traversal: ['D', 'E', 'B', 'F', 'G', 'C', 'A']
Explanation :
- The provided code defines an n-ary tree with nodes containing letters from ‘A’ to ‘G.’
- It demonstrates two types of tree traversal: preorder and postorder.
- Preorder starts from the root (‘A’) and visits nodes before their children, resulting in [‘A’, ‘B’, ‘D’, ‘E’, ‘C’, ‘F’, ‘G’].
- Postorder visits nodes after their children, yielding [‘D’, ‘E’, ‘B’, ‘F’, ‘G’, ‘C’, ‘A’].
N-ary Tree Formula
To find Number of Leaves and Number of Internal Nodes, we have basically two formulas :
In general:
L = (n – 1) * H + 1
Where:
- L is the number of leaf nodes.
- n is the maximum number of children a node can have.
- H is the height of the tree.: The number of internal nodes in an n-ary tree, often denoted as I, can be calculated as:
I = N – L
Where:
- I is the number of internal nodes.
- N is the total number of nodes.
- L is the number of leaf nodes.
To Wrap it up:
In conclusion, N-ary Trees are versatile data structures that offer flexibility in modeling and representing hierarchical relationships in various applications. Their adaptability, combined with efficient traversal and manipulation techniques makes them versatile for real-world applications.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Question 1.
How is an N-ary tree different from a binary tree?
In a binary tree, each node can have at most two children, whereas in an N-ary tree, each node can have up to ‘n’ children, where ‘n’ is not limited to 2.
Question 2.
What is the height of an N-ary tree?
The height of an N-ary tree is the length of the longest path from the root to a leaf node. It can be calculated as logₙ(N), where ‘N’ is the total number of nodes and ‘n’ is the maximum number of children a node can have.
Question 3.
How can I efficiently traverse an N-ary tree with a large number of nodes?
Efficient traversal of N-ary trees can be achieved through well-implemented data structures (e.g., dynamic arrays), caching, and parallel processing techniques.
Question 4.
What is the space complexity of a preorder traversal in an N-ary tree?
The space complexity of a recursive preorder traversal is typically O(H), where H is the height of the tree, and it depends on the depth of the recursion.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
