DSA — Trees

What is a Tree?

A hierarchical data structure with a root node and children.

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []

Tree Terminology

Term	Description
Root	Top node
Parent	Node with children
Child	Node below parent
Leaf	Node with no children
Height	Longest path to leaf
Depth	Distance from root

Tree Traversal

# DFS - Preorder
def preorder(node):
    if node:
        print(node.data)
        for child in node.children:
            preorder(child)

# DFS - Inorder (for binary trees)
def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)

# BFS - Level order
from collections import deque

def level_order(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.data)
        for child in node.children:
            queue.append(child)

Binary Tree

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

Mini Practice

1. Implement a tree node
2. Traverse tree (preorder, inorder, postorder)
3. Count leaf nodes
4. Find tree height

Up Next

Continue with Binary Trees — binary tree operations.